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