Опубликовано 5 лет назад по предмету Информатика от patriot7182

Задача по информатике. Pascal или Delphi с подробным решением и объяснениями!

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

Входные данные
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую
необходимо выдать.

Выходные данные
Программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.

Примеры
входные данные
5
1 3 7 12 32
40
выходные данные
32 7 1

Ответ

Ответ дан vladrus113

var v:array [0..100000] of integer; a:array [0..100,0..100000] of integer; m,p,k,w:integer;
procedure step(z,ma:integer);beginif z>0 then if a[z,ma]<>a[z-1,ma] then if a[z-1,ma]<a[z-1,ma-v[z]]+v[z] then begin step(z-1,ma-v[z]); write(v[z],' '); end else step(z-1,ma) else step(z-1,ma); end;

beginread(k);for p:=1 to k do begin read(v[p]); end;read(w);for p:=1 to k do begin for m:=1 to w do begin if m-v[p]>=0 then a[p,m]:=(max(a[p-1,m-v[p]]+v[p],a[p-1,m])) else a[p,m]:=a[p-1,m]; end; end;if a[k,w]=w then step(k,w) else writeln('No solution');end.
1. Ответ
  
  Ответ дан vladrus113
  
  То есть при выполнении программы со степа я перехожу к самой процедуре и она выполняется в программе. В данном случае эта программа восстанавливает ответ
2. Ответ
  
  Ответ дан vladrus113
  
  Если такое представление не существует, то программа должна вывести строку No solution.
  Вот я и пишу No solution, когда представлений не существует.
3. Ответ
  
  Ответ дан patriot7182
  
  спс, буду пытаться разобраться. А другие есть способы решения, без процедуры?
4. Ответ
  
  Ответ дан vladrus113
  
  да. Но я такое чудо составить сам не смогу. Это называется задача о рюкзаке. Попробуй поискать в интернете. Банкомат - это одна из самых сложных задач этого раздела. Есть подробное обьяснение на http://informatics.mccme.ru/course/view.php?id=9. Раздел "Задача о рюкзаке."
5. Ответ
  
  Ответ дан patriot7182
  
  Задачу про рюкзак решали, надо будет глянуть

Самые новые вопросы

Математика - 5 лет назад

Решите уравнения: а) 15 4 ∕19 + x + 3 17∕19 = 21 2∕19; б) 6,7x - 5,21 = 9,54

Помогите решить задачи на паскаль.1) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти произведение всех элементов массива.2) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти сумму четных элементов массива.3) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти максимальный элемент массива.4) дан массив случайных чисел (количество элементов вводите с клавиатуры). найти максимальный элемент массива среди элементов, кратных 3.

География - 5 лет назад

Почему япония - лидер по выплавке стали?

Математика - 5 лет назад

Чему равно: 1*(умножить)х? 0*х?

Русский язык - 5 лет назад

В каком из предложений пропущена одна (только одна!) запятая?1.она снова умолкла, точно некий внутренний голос приказал ей замолчать и посмотрела в зал. 2.и он понял: вот что неожиданно пришло к нему, и теперь останется с ним, и уже никогда его не покинет. 3.и оба мы немножко удовлетворим свое любопытство.4.впрочем, он и сам только еле передвигал ноги, а тело его совсем застыло и было холодное, как камень. 5.по небу потянулись облака, и луна померкла.

Информация