Remplissage de volumes

On dispose d'un seau d'eau vide et de bouteilles de tailles différentes qui sont remplies d'eau. Quelle est la combinaison de bouteilles dont l'eau, une fois versée dans le seau, le remplit au maximum? Le problème peut être transposé à des chansons qui doivent remplir au mieux une cassette audio. Dans l'exemple suivant on a pris arbitrairement un seau dont le volume est de 1885 et 5 bouteilles dont les volumes sont dans le tableau t.

Une solution à ce problème est donnée en utilisant le programme qui faisait des anagrammes; il suffit de chercher la combinaison de bouteilles qui remplit au mieux un volume donné.

const t: array[1..5] of integer = (250, 370, 451, 749, 634);
 max: longint = 1885;
 
var temoin: string;
 difference: longint;
 nb_bouteilles: integer;
 
procedure anagrammes(st: string; nb1, nb2: byte; result: integer);
var i: byte;
begin
 for i := nb1 to nb2 do
 if difference = 0 then exit else
 if nb2 < nb_bouteilles then anagrammes(st + chr(64 + i), i + 1, nb2 + 1, result + t[i])
 else
 if (max - result - t[i] < difference) and (max - result - t[i] >= 0) then
 begin
 temoin := st + chr(64 + i);
 difference := max - result - t[i];
 form1.memo1.lines.add('meilleure combinaison pour l''instant : ' +
 temoin + ';reste à remplir: ' + inttostr(difference) + ' litres');
 end;
end;
 
procedure recherche;
var i: integer;
 s: string;
begin
 nb_bouteilles := high(t);
 form1.memo1.lines.add('Vous disposez de ' + inttostr(nb_bouteilles) + ' bouteilles.');
 form1.memo1.lines.add('Ces bouteilles sont numérotées avec des lettres.');
 form1.memo1.lines.add('Leurs volumes respectifs sont :');
 for i := 1 to nb_bouteilles do
 form1.memo1.lines.add(chr(64 + i) + '=' + inttostr(t[i]) + ' litres');
 form1.memo1.lines.add('On doit remplir un volume de ' + inttostr(max) + ' litres.');
 for i := 1 to nb_bouteilles do anagrammes('', 1, i, 0);
 form1.memo1.lines.add('');
 s := 'bouteilles = ' + temoin + '; partie remplie = ' + inttostr(max - difference) + ' litres';
 form1.memo1.lines.add(s);
 s := 'reste à remplir = ' + inttostr(difference) + ' litres; maximum remplissable = ' + inttostr(max) + ' litres';
 form1.memo1.lines.add(s);
 s := 'pourcentage de remplissage : ' + inttostr(100 - round(difference * 100 / max)) + ' %';
 form1.memo1.lines.add(s);
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
 difference := max; temoin := '';
 recherche;
end;

Télécharger le code source Delphi