Задача «Разменный автомат»

[Serge_Bliznykov]

Сообщение от Аватар

https://informatics.mccme.ru/mod/book/view.php?id=815
Мельком глянул не вникая ))

спасибо. всё замечательно (за исключением требований к памяти - это я про массив размером n+1, где n- требуемая сумма) и решение через ДП. И решается задача минимизации количества купюр (чего в данной задаче нет).
НО!
Но, к сожалению, там рассматривается более простой случай

Будем считать, что запасы банкнот каждого номинала неограничены.

И наверняка представленное решение можно адаптировать под ограниченное число купюр - нужно завести массив с количеством купюр:

 const int INF=1000000000; // Значение константы }бесконечность} 
 int F[n+1]; 
 F[0]=0; 
 int m, i; 
 for(m=1; m<=n; ++m)   // заполняем массив F 
 {                     // m - сумма, которую нужно выдать 
   F[m]=INF;           // помечаем, что сумму m выдать нельзя 

   <тут надо восстановить исходное значение массива с количеством наличных  купюр>
   for(i=0; i<k; ++i)  // перебираем все номиналы банкнот 
   { 
     if( iя купюра есть в наличие && m>=a[i] && F[m-a[i]]+1<F[m]){
         F[m] = F[m-a[i]]+1; // изменяем значение F[m], если нашли лучший способ выдать сумму m 

         <тут уменьшаем количество i-й купюры на 1>
   }                       
 }

я красным выделил изменения.
я правильно думаю? или я где-то что-то упускаю?

[Аватар]

Я бы так сделал, что поближе, поэтому делфи ))

procedure TForm1.Button3Click(Sender: TObject);
const INF = 1000000000;
var n,k,m,i,j,s: Integer;
    F,a,b,c: array of Integer;
begin
  k:=4;
  SetLength(a,k);  //номиналы
  SetLength(b,k);  //к-во купюр
  SetLength(c,k);  //к-во для выдачи
  a[0]:=50;  b[0]:=40;
  a[1]:=100; b[1]:=2;
  a[2]:=200; b[2]:=2;
  a[3]:=500; b[3]:=1;

  n:=1200;  //сумма
  SetLength(F,n+1);

  for m:=1 to n do begin
    F[m]:=INF;
    for i:=0 to k-1 do begin
      if (b[i]-c[i]>0) and (m>=a[i]) and (F[m-a[i]]+1<F[m]) then begin
        F[m]:=F[m-a[i]]+1;
        s:=m;
        for j:=0 to k-1 do c[j]:=0;
        while s>0 do
          for j:=0 to k-1 do
            if F[s-a[j]]=F[s]-1 then begin
              Inc(c[j]);
              Dec(s,a[j]);
              Break;
            end;
      end;
    end;
  end;

  if F[n]=INF then Memo1.Lines.Add('нельзя')
  else begin
    Memo1.Lines.Add(Format('%d',[F[n]]));
    for i:=0 to k-1 do Memo1.Lines.Add(Format('%d - %d',[a[i],c[i]]));
  end;
end;

[Serge_Bliznykov]

Сообщение от Аватар

Я бы так сделал, что поближе, поэтому делфи ))

работает отлично.
большое спасибо!

[ADSoft]

вот у нас в банкоматах 3 алгоритма было
- минимизация. Выдача минимально возможным кол-вом купюр. Начинали выдачу максимальными, если не получалось уменьшали номинал купюры
- выравнивание кассет. Такая выдача, чтоб из кассет равномерно бралось.
- размен. Противоположность первому алгоритму - размен мелкими купюрами

[Аватар]

Почти тоже самое, что вижу сейчас на многих банкоматах: крупными, средними, мелкими.
2-ой пункт правда не очень выравнивание кассет ))
Да и в банкоматах чаще всего один-два номинала