Lección 16 · 16 de 20

Recursión y backtracking · Pascal

Resuelva problemas de búsqueda con recursión y backtracking en Pascal: qué facturas pendientes suman exactamente el importe de un pago.

Pascal · Recursión y backtracking en DMarlon Studio: el código del ejemplo y su salida en la terminal

Un cliente paga 500 EUR y hay seis facturas pendientes: ¿qué combinaciones suman justo ese importe? Es un caso real de conciliación bancaria y un ejemplo perfecto de backtracking (vuelta atrás): probar una opción, seguir explorando y, si no lleva a nada, deshacerla y probar la siguiente.

Search(i, remaining) decide sobre la factura i sabiendo cuánto falta por cubrir. Tiene dos casos base, los que detienen la recursión: si remaining llega a 0, la selección actual es una solución y se escribe; si se acaban las facturas o el importe se pasa (queda negativo), ese camino es un callejón sin salida y se vuelve atrás con Exit.

El corazón está en las cuatro últimas líneas: se elige la factura (chosen[i] := True) y se explora el resto con lo que falta; después se deshace la elección (chosen[i] := False) y se explora el resto sin ella. Así se recorren todas las combinaciones, 2⁶ = 64 como mucho, y se descartan pronto las que se pasan.

El array chosen es el estado compartido que se va marcando y desmarcando, y found cuenta las soluciones; Free Pascal permite inicializar una variable global al declararla, como en found: Integer = 0. El resultado: cuatro maneras distintas de casar el pago.

Código · main.pas

program main;const  Invoices: array[0..5] of Integer = (120, 340, 90, 160, 250, 40);  Payment = 500;var  chosen: array[0..5] of Boolean;  found: Integer = 0;procedure Search(i, remaining: Integer);var k: Integer;begin  if remaining = 0 then  // a match: print the chosen invoices  begin    Inc(found);    Write('Option ', found, ':');    for k := 0 to High(Invoices) do      if chosen[k] then Write(' ', Invoices[k]);    WriteLn;    Exit;  end;  if (i > High(Invoices)) or (remaining < 0) then Exit;  // dead end: go back  chosen[i] := True;             // try with invoice i...  Search(i + 1, remaining - Invoices[i]);  chosen[i] := False;            // ...undo, and try without it  Search(i + 1, remaining);end;begin  Search(0, Payment);  WriteLn(found, ' ways to match a payment of ', Payment);end.

Salida · fpc main.pas && ./main

Option 1: 120 340 40
Option 2: 120 90 250 40
Option 3: 340 160
Option 4: 90 160 250
4 ways to match a payment of 500

Para recordar

Una función recursiva se llama a sí misma con un problema más pequeño.
Los casos base detienen la recursión.
Backtracking: elegir, explorar y deshacer.
Cortar pronto los caminos imposibles ahorra trabajo.
El estado compartido se marca antes y se desmarca después.

Ejercicio

Haga que la búsqueda se detenga en cuanto encuentre la primera combinación y que, en lugar de las facturas, escriba sus posiciones en el array.