Условия: В некотором государстве в обращении находятся банкноты определенных номиналов....

Question

296 просмотров

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

Входные данные: Первая строка входных данных содержит натуральное число n, 0Количество различных видов номиналов). Вторая строка входных данных содержит n различных натуральных чисел x_{1}, x_{2}, x_{3}...,x_{n} (Значения номиналов банкнот), не превосходящих 1000000. Третья строчка содержит натуральное число S, не превосходящее 5000000 (Сумма, которую нужно выдать)

Выходные данные: Программа должна найти представление числа S в виде суммы слагаемых из множества {x_{i}}, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести слово NO.

Пример:

Входные данные:

5

1 3 7 12 32

40

Выходные:

1 7 32

Входные:

5

5 10 50 100 500

99

Выходные:

NO

Помогите, я уже мозг сломал себе, я не хочу списать Я ХОЧУ ПОНЯТЬ!!!

Информатика FGSBHsfg_zn (23 баллов) 19 Март, 18 | 296 просмотров

Дан 1 ответ

Правильный ответ

Такой вариант на простом паскале со стратегией жадность

var
    n, s, i: integer;
    x: array[1..100]of integer;
    answer: string;

begin
    readln(n);
    for i := 1 to n do
        read(x[i]);
    readln(s);

    answer := IntToStr(s) + ' = ';
    for i := n downto 1 do
    begin
        answer := answer + IntToStr(s div x[i]) + '*' + IntToStr(x[i]);
        s := s mod x[i];
        if i > 1 then
            answer := answer + ' + ';
    end;

    if s <> 0 then
        writeln('NO')
    else
        writeln(answer);
end.

Более полный и правильный вариант решения, но и куда более сложный

//PascalABC.Net 3.1 сборка 1200
uses System.Collections.Generic;
uses System;
var
    x := new List;
    c := new List>;

procedure getParcelling(sum, step: integer; coefficients: string; count: integer);
begin
    if step >= x.Count then begin
        if sum = 0 then c.Add((coefficients, count));
        Exit;
    end;
    if step < 0 then step := 0;

    for var j := 0 to (sum div x[step]) do
    begin
        var s := '';
        if j > 0 then begin
            if step > 0 then s += ' + ';
            s += IntToStr(j) + '*' + IntToStr(x[step]);
        end;
        getParcelling(sum - x[step] * j, step + 1, coefficients + s, count + j);
    end;
end;

begin
    x := ReadArrInteger('x:', ReadInteger('n =')).ToList;
    var sum := ReadInteger('sum =');

    getParcelling(sum, 0, '', 0);
    if c.Count = 0 then
        writeln('No')
    else begin
        var min := c.Min(cc -> cc.Item2);
        Println(c.Where(cc -> cc.Item2 = min));
    end;
end.

archery_zn (53.1k баллов) 19 Март, 18