Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > PHP
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.07.2017, 10:56   #11
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
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>
   }                       
 }

я красным выделил изменения.
я правильно думаю? или я где-то что-то упускаю?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 25.07.2017, 12:51   #12
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Я бы так сделал, что поближе, поэтому делфи ))
Код:
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;
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 25.07.2017, 13:33   #13
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Я бы так сделал, что поближе, поэтому делфи ))
работает отлично.
большое спасибо!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 25.07.2017, 14:41   #14
ADSoft
Старожил
 
Регистрация: 25.02.2007
Сообщений: 4,150
По умолчанию

вот у нас в банкоматах 3 алгоритма было
- минимизация. Выдача минимально возможным кол-вом купюр. Начинали выдачу максимальными, если не получалось уменьшали номинал купюры
- выравнивание кассет. Такая выдача, чтоб из кассет равномерно бралось.
- размен. Противоположность первому алгоритму - размен мелкими купюрами
ADSoft на форуме Ответить с цитированием
Старый 25.07.2017, 14:49   #15
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Почти тоже самое, что вижу сейчас на многих банкоматах: крупными, средними, мелкими.
2-ой пункт правда не очень выравнивание кассет ))
Да и в банкоматах чаще всего один-два номинала
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
конечный автомат fkty Помощь студентам 18 17.01.2015 18:49
автомат crechet51 Microsoft Office Excel 8 08.10.2012 02:04
автомат crechet51 Помощь студентам 0 07.10.2012 01:50
Клеточный автомат Munya Фриланс 4 08.05.2010 13:34
Клеточный автомат Noor Помощь студентам 4 29.11.2007 09:19