vadimr Nov 20 2024 at 15:38

Задача о банкомате

Medium

12 min

16K

Programming*Algorithms*Entertaining tasksLisp*

Tutorial

+36

127

Comments 127

Pinned comments

wataru Nov 21 2024 at 12:39

Вообще, для такой маленькой суммы решение работает за миллисекунды и находит следующие решия длины 14:

155 решений

477 477 477 477 477 477 427 427 425 425 425 425 425 408
477 477 477 477 477 477 427 427 427 425 425 425 423 408
477 477 477 477 477 477 427 427 427 427 425 423 423 408
477 477 477 477 477 477 427 427 427 427 425 425 421 408
477 477 477 477 477 477 427 427 427 427 427 423 421 408
477 477 477 477 477 477 427 427 427 427 427 425 419 408
477 477 477 477 477 477 427 427 427 427 427 427 417 408
477 477 477 477 477 477 429 425 425 425 425 425 425 408
477 477 477 477 477 477 429 427 425 425 425 425 423 408
477 477 477 477 477 477 429 427 427 425 425 423 423 408
477 477 477 477 477 477 429 427 427 425 425 425 421 408
477 477 477 477 477 477 429 427 427 427 423 423 423 408
477 477 477 477 477 477 429 427 427 427 425 423 421 408
477 477 477 477 477 477 429 427 427 427 425 425 419 408
477 477 477 477 477 477 429 427 427 427 427 421 421 408
477 477 477 477 477 477 429 427 427 427 427 423 419 408
477 477 477 477 477 477 429 427 427 427 427 425 417 408
477 477 477 477 477 477 429 429 425 425 425 423 423 408
477 477 477 477 477 477 429 429 425 425 425 425 421 408
477 477 477 477 477 477 429 429 427 425 423 423 423 408
477 477 477 477 477 477 429 429 427 425 425 423 421 408
477 477 477 477 477 477 429 429 427 425 425 425 419 408
477 477 477 477 477 477 429 429 427 427 423 423 421 408
477 477 477 477 477 477 429 429 427 427 425 421 421 408
477 477 477 477 477 477 429 429 427 427 425 423 419 408
477 477 477 477 477 477 429 429 427 427 425 425 417 408
477 477 477 477 477 477 429 429 427 427 427 421 419 408
477 477 477 477 477 477 429 429 427 427 427 423 417 408
477 477 477 477 477 477 429 429 429 423 423 423 423 408
477 477 477 477 477 477 429 429 429 425 423 423 421 408
477 477 477 477 477 477 429 429 429 425 425 421 421 408
477 477 477 477 477 477 429 429 429 425 425 423 419 408
477 477 477 477 477 477 429 429 429 425 425 425 417 408
477 477 477 477 477 477 429 429 429 427 423 421 421 408
477 477 477 477 477 477 429 429 429 427 423 423 419 408
477 477 477 477 477 477 429 429 429 427 425 421 419 408
477 477 477 477 477 477 429 429 429 427 425 423 417 408
477 477 477 477 477 477 429 429 429 427 427 419 419 408
477 477 477 477 477 477 429 429 429 427 427 421 417 408
477 477 477 477 477 477 429 429 429 429 421 421 421 408
477 477 477 477 477 477 429 429 429 429 423 421 419 408
477 477 477 477 477 477 429 429 429 429 423 423 417 408
477 477 477 477 477 477 429 429 429 429 425 419 419 408
477 477 477 477 477 477 429 429 429 429 425 421 417 408
477 477 477 477 477 477 429 429 429 429 427 417 419 408
477 477 477 477 477 477 429 429 429 429 429 417 417 408
477 477 477 477 477 477 431 425 425 425 425 425 423 408
477 477 477 477 477 477 431 427 425 425 425 423 423 408
477 477 477 477 477 477 431 427 425 425 425 425 421 408
477 477 477 477 477 477 431 427 427 425 423 423 423 408
477 477 477 477 477 477 431 427 427 425 425 423 421 408
477 477 477 477 477 477 431 427 427 425 425 425 419 408
477 477 477 477 477 477 431 427 427 427 423 423 421 408
477 477 477 477 477 477 431 427 427 427 425 421 421 408
477 477 477 477 477 477 431 427 427 427 425 423 419 408
477 477 477 477 477 477 431 427 427 427 425 425 417 408
477 477 477 477 477 477 431 427 427 427 427 421 419 408
477 477 477 477 477 477 431 427 427 427 427 423 417 408
477 477 477 477 477 477 431 429 425 425 423 423 423 408
477 477 477 477 477 477 431 429 425 425 425 423 421 408
477 477 477 477 477 477 431 429 425 425 425 425 419 408
477 477 477 477 477 477 431 429 427 423 423 423 423 408
477 477 477 477 477 477 431 429 427 425 423 423 421 408
477 477 477 477 477 477 431 429 427 425 425 421 421 408
477 477 477 477 477 477 431 429 427 425 425 423 419 408
477 477 477 477 477 477 431 429 427 425 425 425 417 408
477 477 477 477 477 477 431 429 427 427 423 421 421 408
477 477 477 477 477 477 431 429 427 427 423 423 419 408
477 477 477 477 477 477 431 429 427 427 425 421 419 408
477 477 477 477 477 477 431 429 427 427 425 423 417 408
477 477 477 477 477 477 431 429 427 427 427 419 419 408
477 477 477 477 477 477 431 429 427 427 427 421 417 408
477 477 477 477 477 477 431 429 429 423 423 423 421 408
477 477 477 477 477 477 431 429 429 425 423 421 421 408
477 477 477 477 477 477 431 429 429 425 423 423 419 408
477 477 477 477 477 477 431 429 429 425 425 421 419 408
477 477 477 477 477 477 431 429 429 425 425 423 417 408
477 477 477 477 477 477 431 429 429 427 421 421 421 408
477 477 477 477 477 477 431 429 429 427 423 421 419 408
477 477 477 477 477 477 431 429 429 427 423 423 417 408
477 477 477 477 477 477 431 429 429 427 425 419 419 408
477 477 477 477 477 477 431 429 429 427 425 421 417 408
477 477 477 477 477 477 431 429 429 427 427 417 419 408
477 477 477 477 477 477 431 429 429 429 421 421 419 408
477 477 477 477 477 477 431 429 429 429 423 419 419 408
477 477 477 477 477 477 431 429 429 429 423 421 417 408
477 477 477 477 477 477 431 429 429 429 425 417 419 408
477 477 477 477 477 477 431 429 429 429 427 417 417 408
477 477 477 477 477 477 431 431 425 423 423 423 423 408
477 477 477 477 477 477 431 431 425 425 423 423 421 408
477 477 477 477 477 477 431 431 425 425 425 421 421 408
477 477 477 477 477 477 431 431 425 425 425 423 419 408
477 477 477 477 477 477 431 431 425 425 425 425 417 408
477 477 477 477 477 477 431 431 427 423 423 423 421 408
477 477 477 477 477 477 431 431 427 425 423 421 421 408
477 477 477 477 477 477 431 431 427 425 423 423 419 408
477 477 477 477 477 477 431 431 427 425 425 421 419 408
477 477 477 477 477 477 431 431 427 425 425 423 417 408
477 477 477 477 477 477 431 431 427 427 421 421 421 408
477 477 477 477 477 477 431 431 427 427 423 421 419 408
477 477 477 477 477 477 431 431 427 427 423 423 417 408
477 477 477 477 477 477 431 431 427 427 425 419 419 408
477 477 477 477 477 477 431 431 427 427 425 421 417 408
477 477 477 477 477 477 431 431 427 427 427 417 419 408
477 477 477 477 477 477 431 431 429 423 423 421 421 408
477 477 477 477 477 477 431 431 429 423 423 423 419 408
477 477 477 477 477 477 431 431 429 425 421 421 421 408
477 477 477 477 477 477 431 431 429 425 423 421 419 408
477 477 477 477 477 477 431 431 429 425 423 423 417 408
477 477 477 477 477 477 431 431 429 425 425 419 419 408
477 477 477 477 477 477 431 431 429 425 425 421 417 408
477 477 477 477 477 477 431 431 429 427 421 421 419 408
477 477 477 477 477 477 431 431 429 427 423 419 419 408
477 477 477 477 477 477 431 431 429 427 423 421 417 408
477 477 477 477 477 477 431 431 429 427 425 417 419 408
477 477 477 477 477 477 431 431 429 427 427 417 417 408
477 477 477 477 477 477 431 431 429 429 421 419 419 408
477 477 477 477 477 477 431 431 429 429 421 421 417 408
477 477 477 477 477 477 431 431 429 429 423 417 419 408
477 477 477 477 477 477 431 431 429 429 425 417 417 408
477 477 477 477 477 477 431 431 431 423 421 421 421 408
477 477 477 477 477 477 431 431 431 423 423 421 419 408
477 477 477 477 477 477 431 431 431 423 423 423 417 408
477 477 477 477 477 477 431 431 431 425 421 421 419 408
477 477 477 477 477 477 431 431 431 425 423 419 419 408
477 477 477 477 477 477 431 431 431 425 423 421 417 408
477 477 477 477 477 477 431 431 431 425 425 417 419 408
477 477 477 477 477 477 431 431 431 427 421 419 419 408
477 477 477 477 477 477 431 431 431 427 421 421 417 408
477 477 477 477 477 477 431 431 431 427 423 417 419 408
477 477 477 477 477 477 431 431 431 427 425 417 417 408
477 477 477 477 477 477 431 431 431 429 419 419 419 408
477 477 477 477 477 477 431 431 431 429 421 417 419 408
477 477 477 477 477 477 431 431 431 429 423 417 417 408
477 477 477 477 477 477 431 431 431 431 417 419 419 408
477 477 477 477 477 477 431 431 431 431 421 417 417 408
477 477 477 477 477 477 477 417 417 417 417 417 417 408
477 477 477 477 477 477 477 423 421 421 421 408 408 408
477 477 477 477 477 477 477 423 423 421 419 408 408 408
477 477 477 477 477 477 477 423 423 423 417 408 408 408
477 477 477 477 477 477 477 425 421 421 419 408 408 408
477 477 477 477 477 477 477 425 423 419 419 408 408 408
477 477 477 477 477 477 477 425 423 421 417 408 408 408
477 477 477 477 477 477 477 425 425 417 419 408 408 408
477 477 477 477 477 477 477 427 421 419 419 408 408 408
477 477 477 477 477 477 477 427 421 421 417 408 408 408
477 477 477 477 477 477 477 427 423 417 419 408 408 408
477 477 477 477 477 477 477 427 425 417 417 408 408 408
477 477 477 477 477 477 477 429 419 419 419 408 408 408
477 477 477 477 477 477 477 429 421 417 419 408 408 408
477 477 477 477 477 477 477 429 423 417 417 408 408 408
477 477 477 477 477 477 477 431 417 419 419 408 408 408
477 477 477 477 477 477 477 431 421 417 417 408 408 408
477 477 477 477 477 477 477 477 477 477 431 431 431 186
477 477 477 477 477 477 477 477 477 477 477 408 408 186

Полный перебор с оптимизацией через ДП

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int S = 6249;
const int N = 12;
const int a[N] = {83, 186, 408, 419, 417, 421, 423, 425, 427, 429, 431, 477};
// dp[i][j] = минимальное количество купюр среди первых i номиналов, чтобы набрать сумму j.
int dp[N+1][S+1];

int total_count = 0;

void PrintAll(int s, int n, vector<int> &coins) {
    if (s == 0) {
        for (size_t i = 0; i < coins.size(); ++i) {
            cout << coins[i] << " ";
        }
        cout << "\n";
        ++total_count;
        return;
    }
    // Пробуем не брать максимальную купюру вообще.
    if (n > 0 && dp[n-1][s] == dp[n][s]) PrintAll(s, n-1, coins);
    // Пробуем взять максимальную купюру один раз.
    if (s >= a[n-1] && dp[n][s-a[n-1]] == dp[n][s]-1) {
        coins.push_back(a[n-1]);
        PrintAll(s-a[n-1], n, coins);
        coins.pop_back();
    }
}

int main() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= S; ++j) {
            // всегда можно просто не брать максимальную купюру.
            dp[i][j] = dp[i-1][j];
            if (j < a[i-1]) {
                continue;
            }
            int prev = dp[i][j-a[i-1]];
            // если берем максимальную купюру, то только если через нее короче.
            if (prev != -1 && (dp[i][j] == -1 || dp[i][j] > prev + 1)) {
                dp[i][j] = prev + 1;
            }
        }
    }
    
    cout << "lenth: " << dp[N][S] << "\n";
    
    vector<int> solution;
    PrintAll(S, N, solution);
    cout << "total count: " << total_count << "\n";
    return 0;
}

Akina Nov 20 2024 at 16:01

Мне кажется, что вместо динамического программирования вы описываете простейший поиск в ширину...

vadimr Nov 20 2024 at 16:04

Поиск в ширину и есть пример динамического программирования.

Akina Nov 20 2024 at 16:16

Да? вот как-то странно... я лично вашем решении вот в упор не вижу разделения на простые подзадачи, хоть убейся. Есть одна-единственная подзадача, которая у вас сформулирована как "мы строим список всех решений следующего уровня, добавляя каждую из возможных купюр к каждому из возможных решений текущего уровня". Вы с неё начинаете (текущий уровень нулевой, список решений пуст), и её же решаете на каждом очередном шаге. Коли эдак рассуждать, так и самая обычная рекурсия тоже окажется динамическим программированием.

vadimr Nov 20 2024 at 16:22

Обычно принято считать, что рекурсия отличается от динамического программирования в операционной семантике только направлением движения . В ДП – от простого к сложному, в рекурсии – от сложного к простому.

Если рекурсию рассматривать чисто денотационно, то есть просто как способ записи рекуррентной связи между постановкой задачи и результатом, то она эквивалентна ДП.

В зависимости от характера задачи, может оказаться выгоднее двигаться в ту или иную сторону.

Но вообще строгого математического определения ДП, в отличие от рекурсии, я не видел.

rblaze Nov 28 2024 at 22:14

Динамическое программирование отличается от рекурсии кешированием промежуточных результатов, если я правильно понимаю.

vadimr Nov 29 2024 at 04:32

Рекурсия тоже может быть с мемоизацией.

wataru Nov 29 2024 at 11:02

Рекурсия с мемоизацией ничем принципиально не отличается от алгоритма, полученного по методу динамического программирования. Так что можно считать любую рекурсию с мемоизацией ДП.

vadimr Nov 29 2024 at 11:17

ДП работает от малых задач к большим, рекурсия с мемоизацией - от исходной большой задачи к малым.

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

wataru Nov 29 2024 at 12:27

Смотрте, ДП - это когда у вас задача решается через подзадачи. Для ДП вам надо параметризировать задачу и определить 3 вещи:

1) База: ответ для каких-то, обычно, маленьких задач.

2) Рекуррентное соотношение: как ответ к задаче можно пересчитать через ответы к другим задачам.

3) Ответ: какая из множества задач соотвествует вашей исходной.

Вот вся суть динамического программирования. А уже это можно реализовывать как вам удобнее: рекурсией с мемоизацией сверху вниз, циклами снизу-вверх, обходом в ширину с очередью или волновым алгоритмом. Хранить значения можно в матрице, хеш-таблице, сбалансированном дереве или даже в кеше. Можно хранить не все значения, а только последнюю строку или столбец. Можно параллельно считать несколько функций сразу.

Но это все еще остается динамическим программированием. ДП - это НЕ циклы рассчитывающие какую-то матрицу, хотя это частый вариант его реализации. ДП - подход к решению задач, если хотите.

Поэтому рекурсия с мемоизацией 100% соответствует какому-то ДП, потому что рекурсия имеет какую-то базу, задает какое-то рекурретное соотношение, а как вы его вызываете в программе - задает ответ.

vadimr Nov 29 2024 at 12:42

Всё-таки это не совсем так, потому что рекурсия может и не иметь базы. Как, например, в задаче 3x+1 (Коллатца).

wataru Nov 29 2024 at 12:43

А как в такой рекурсии работает мемоизация? Если там нет базы, как она вообще останавливается?

vadimr Nov 29 2024 at 12:49

А как в такой рекурсии работает мемоизация?

Мемоизации, для того чтобы работать вообще, не обязательно работать конкретно в каждом случае.

Если там нет базы, как она вообще останавливается?

А мы не знаем, остановится она или нет. Только предполагаем.

wataru Nov 29 2024 at 13:14

Я так понимаю, что база там есть. Когда достигли 1. Но вот мы не знаем, достигает ли ее все состояния. В этом случае - это тоже реализация ДП. Вот только оно корректно если гипотеза выполняется. В противном случае оно виснет. Т.е. если гипотеза не выполняется, то тут просто нельзя было применять ДП. Но это все еще ДП "достигает ли это число 1".

Mingun Nov 29 2024 at 07:39

Я думаю, что динамическое программирование (ДП) -- подход, а рекурсия -- конкретная его реализация. ДП можно реализовать и без рекурсии, с помощью цикла

vadimr Nov 29 2024 at 08:12

Тут всё упирается в конкретное понимание термина "рекурсия".

Если понимать узко, как синтаксическую запись рекурсивного фунционального вызова в исходном тексте программы, то для языка Scheme вопрос вообще не имеет смысла, так как в нём рекурсивный вызов является единственным формализмом для организации повторяющихся вычислений, а цикл представляет собой макроопределение, развёртывающееся в рекурсивный вызов. А на уровне машинного кода всё это превращается в нерекурсивные условные переходы.

Но в целом, когда мы говорим о рекурсии, то в широком смысле не обязательно подразумеваем именно сам рекурсивный функциональный вызов. Можно говорить просто о рекурсивном алгоритме.

Здесь я использовал термин "рекурсия" в алгоритмическом, а не синтаксическом смысле. Синтаксически же рекурсия будет присуща любому повторяющемуся вычислению в языке Scheme, в том числе и любой реализации ДП.

Spaceoddity Nov 20 2024 at 16:27

Это же диофантов анализ в чистом виде))

vadimr Nov 20 2024 at 16:29

Непонятно, как на диофантовом анализе ввести критерий минимизации.

Spaceoddity Nov 21 2024 at 19:20

В смысле? Решение задачи по арифметике сводится к поиску всех решений этой задачи или доказательству отсутствия таких решений.

А уж выбрать потом из этих решений те, которые удовлетворяют заданным критериям или отсортировать их по какому-то параметру...

vadimr Nov 21 2024 at 20:20

Что вы подразумеваете под решением с точки зрения диофантова анализа? Я так понимаю, что это будут просто любые корни уравнения сложения купюр в заданную сумму, без учёта длины цепочки. А их просто море. Такое “решение” тривиально и никак не упрощает изначальную задачу.

Spaceoddity Nov 21 2024 at 23:43

Вы хотите решать задачу теоретически или практически? Для теоретической - вы довольно быстро скатились к примерам с реальными номиналами.

Для практической формулировки у вас слишком крутые допущения:

их там неограниченно много. Такое допущение принципиально ничего не меняет в решении задачи, но несколько упрощает код.

Лол, кек, как говорится.
Ну и непонятно требование:

Необходимо найти все варианты выдачи этой суммы минимальным количеством купюр.

Зачем вам вдруг все варианты? Вам нужен один - оптимальный. Если же вы хотите выбирать из всех вариантов те, которые укладываются в ваш изначальный запас купюр, то первым делом надо убирать из формулировки "непринципиальное допущение", а во-вторых - подходить к решению задачи тут уже надо отталкиваясь от вводных "запаса купюр".

В общем, что для математики, что для программирования - слишком размытая и неоднозначная формулировка.

vadimr Nov 21 2024 at 23:46

Формулировка задачи совершенно однозначна.

Её решение с точки зрения выбора алгоритма никак не меняется от учёта запаса купюр, за исключением одного момента, который рассмотрен в статье. Поэтому добавлять в код учёт запаса не имеет никакого дидактического смысла, это просто лишняя невалифицированная работа руками.

wataru Nov 21 2024 at 23:55

Согласен с комментатором выше - такая задача странна. Она имеет право быть, конечно, но она бесполезна для практики. Если вам нужно минимальное количество купюр в ответе - то вам нужен один оптимальный ответ. Если вам нужна куча вариантов, то логично спросить вообще все возможные варианты размена, а не только варианты кратчайшей длины.

С теоретической точки зрения эта задача не сложнее перебора вообще всех вариантов и тоже не представляет особой ценности. Алгоритм практически такой же и работает за практически то же самое время, ведь размер ответа итак экспоненциален даже с ограничением на оптимальный размен.

На литкоде не просят все варианты, а лишь один. А если вам хочется продемонстрировать применение amb в scheme, то перебор вообще всех вариантов размена точно так же сработал бы.

vadimr Nov 21 2024 at 23:57

Тут проявляется разница между денотационной и операционной семантикой. Это вопрос теоретического программирования, которому я вообще уделяю большое внимание.

По-простому говоря, это связано с тем, зачем вообще нужны отсечения в продукционном выводе.

А то можно докопаться и до силлогизмов типа “все люди смертны, X человек”, как не имеющих практической ценности.

vadimr Nov 22 2024 at 09:46

Встаёт, кстати, другой интересный вопрос: можно ли ваш динамический обход по длине цепочки адаптировать на случай учёта запаса купюр? Ведь он вроде бы как абстрагирован от множества купюр.

wataru Nov 22 2024 at 11:12

Можно. Будет немного медленнее работать динамика, ибо количество оставшихся купюр придется учитывать, но все делается.

Например, стандартная постановка задачи размена монет как раз такая - у вас есть множество монет, каждую можно использовать по одному разу (монеты могут и совпадать). И ДП там практически такое же.

vadimr Nov 22 2024 at 11:16

ДП-то такое же, но у множества монет гораздо больше количество комбинаций, чем у множества их номиналов.

wataru Nov 22 2024 at 11:22

В любом случае, самое медленное - вывод ответа. Перебор с идеальными отсечениями работает ровно за это время. Т.е. это самое быстрое решение, которое вообще может быть.

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

Если вам надо только подсчитать все варианты, то тут и перебора не надо - ДП с этим справится само.

vadimr Nov 22 2024 at 11:30

Мой вопрос состоит в том, получится ли размерность матрицы в таком случае равной S*(количество отдельных купюр в банкомате), или можно как-то сэкономить? Иными словами, что будет индексом для строк вашей матрицы dp?

Если учитывать именно отдельные купюры, то по сравнению с этим можно значительно сэкономить, так как включения в выдачу купюр одинакового номинала эквивалентны.

wataru Nov 22 2024 at 20:24

так как включения в выдачу купюр одинакового номинала эквивалентны.

Если так, то ДП элементарно фиксится: 2 перехода будут 1) пропустить текущую купюру 2) взять все оставшиеся купюры этого номинала (вместо пропустить текущую или взять ее одну).

Тут в матрице все еще будет S*(количество отдельных купюр в банкомате) строк. Ее можно сократить до S*(количество номиналов), но там появится третий цикл до (количество купюры данного номинала), так что ДП будет занимать все то же самое время, хотя памяти потреблять заметно меньше. Тут переходы будут "взять k=0..m купюр данного номинала и перейти к следующему".

Но, опять же, на больших тестах сам ответ будет гораздо больше, ибо там экспоненциально много вариантов.

Код

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int S = 15;
const int N = 10;
const int a[N] = {1,1,1,1,2,2,2,3,3,3};
// dp[i][j] = минимальное количество купюр среди первых i номиналов, чтобы набрать сумму j.
int dp[N+1][S+1];
// количество купюр данного номинала.
int cnt[N];
int total_count = 0;

void PrintAll(int s, int n, vector<int> &coins) {
    if (s == 0) {
        for (size_t i = 0; i < coins.size(); ++i) {
            cout << coins[i] << " ";
        }
        cout << "\n";
        ++total_count;
        return;
    }
    // Пробуем не брать максимальную купюру вообще.
    if (n > 0 && dp[n-1][s] == dp[n][s]) PrintAll(s, n-1, coins);
    // Пробуем взять максимальную купюру.
    int total = cnt[n-1]*a[n-1];
    if (s >= total && dp[n-cnt[n-1]][s-total] == dp[n][s]-cnt[n-1]) {
        for (int k = 0; k < cnt[n-1]; ++k)
            coins.push_back(a[n-1]);
        PrintAll(s-total, n-cnt[n-1], coins);
        coins.resize(coins.size()-cnt[n-1]);
    }
}

int main() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    cnt[0] = 1;
    for(int i = 1; i < N; ++i) {
        if (a[i] != a[i-1]) cnt[i] = 1;
        else cnt[i] = cnt[i-1]+1;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= S; ++j) {
            // всегда можно просто не брать максимальную купюру.
            dp[i][j] = dp[i-1][j];
            int total = a[i-1]*cnt[i-1];
            if (j < total) {
                continue;
            }
            int prev = dp[i-cnt[i-1]][j-total];
            // если берем максимальные купюры, то только если через нее короче.
            if (prev != -1 && (dp[i][j] == -1 || dp[i][j] > prev + cnt[i-1])) {
                dp[i][j] = prev + cnt[i-1];
            }
        }
    }
    
    cout << "lenth: " << dp[N][S] << "\n";
    
    vector<int> solution;
    PrintAll(S, N, solution);
    cout << "total count: " << total_count << "\n";
    return 0;
}

vadimr Nov 22 2024 at 21:13

Всё верно, но если у нас в кассете банкомата заложено гораздо больше купюр, чем в нужно в выдаче (как и в реальной жизни), то при какой-то ёмкости кассеты с деньгами расписывать всю эту матрицу окажется более накладно, чем просто перебирать купюры с отсечением. Можно сказать то же самое по-другому: дополнительные купюры в кассете сверх суммы выдачи ничего не меняют в переборе купюр с отсечением, но увеличивают матрицу.

Это произойдёт, если, например, добавить в ваш массив a[] миллиард троек при сохранении S=15.

wataru Nov 22 2024 at 21:22

то при какой-то ёмкости кассеты с деньгами расписывать всю эту матрицу окажется более накладно, чем просто перебирать купюры с отсечением.

Вопрос, с каким отсечением? Я трачу полиномиальное время на предподсчет, чтобы иметь идеальное отсечение в переборе. Вы не тратите время на предподсчет, но ваши отсечения заходят в "тупики". Вопрос в том, как много их будет. Мне кажется, что в огромном дереве перебора, где экспоненциальное количество вариантов, их весьма много.

Давайте что ли на больших числах запустим ваш и мой алгоритм и померяемся, чтобы точку поставить в этой дискуссии? Правда сложно будет сравнивать с++ и scheme, но если там разница в десятки а то и сотни раз окажется - то это не объяснить более быстрым языком.

vadimr Nov 22 2024 at 21:29

Так в том-то и дело, что моё дерево перебора вообще не зависит от количества банкнот в кассете, пока их достаточно. У меня же не будет списка всех банкнот, по которому мне пришлось бы путешествовать, а будет примерно такой список:

((5000 . 1000000000) (2000 . 500000000) (1000 . 1500000000) (500 . 1000000000) (200 . 3333333333) (100 . 777777777))

с номиналами и количеством. Где я просто буду уменьшать счётчик при взятии купюры и проверять, что он не ушёл в минус. Почему я и писал, что описанные в статье алгоритмы не зависят от опции подсчёта купюр.

Если хотите, можно попробовать померяться, но это, вроде, ясно из общих соображений.

wataru Nov 22 2024 at 21:38

Зависит же! Чем больше у вас банкнот, тем глубже вы можете зайти, беря эту банктноту. Вы же перебираете, сколько их брать как-то? Т.е. дерево становится выше. И в каждой вершине есть развилка. Количество путей экспоненциально растет!

vadimr Nov 22 2024 at 21:41

Захожу-то я в глубину только до суммы выдачи, а не до ёмкости кассеты. Как только ветка дерева превысила сумму выдачи, я отсекаюсь. Если мне надо получить на руки 10000 рублей, то я и перебираю денежное дерево только до 10000 на руках, и миллиард или гугол в кассете меня не волнует.

wataru Nov 22 2024 at 22:01

Захожу-то я в глубину только до суммы выдачи, а не до ёмкости кассеты.

Ну так это же тривиальная оптимизация! Я ее тоже запросто могу прикрутить - выкинув из входных данных лишние купюры и все.

vadimr Nov 22 2024 at 22:04

Логично.

wataru Nov 22 2024 at 21:59

Вот тест:

S = 15837
N = 46
a = {1,1,1,5,5,5,5,5,9,9,9,12,12,16,16,37,37,37,76,76,76,85,85,85,200,200,200,200,545,672,676,676,680,680,954,954,954,954,954,954,954,954,1040,1040,2500,2500}

Ответ:

length: 17
2500 2500 1040 954 954 954 954 954 954 954 954 680 680 676 76 37 16 
2500 2500 1040 1040 954 954 954 954 954 954 954 676 672 545 85 85 16 
2500 2500 1040 1040 954 954 954 954 954 954 954 676 676 545 85 85 12 
2500 2500 1040 1040 954 954 954 954 954 954 954 676 676 672 37 9 9 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 672 545 85 85 12 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 676 672 37 9 5 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 676 676 37 5 5 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 676 676 37 9 1 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 680 672 37 5 5 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 680 672 37 9 1 
2500 2500 1040 1040 954 954 954 954 954 954 954 680 680 676 37 5 1 
2500 2500 1040 1040 954 954 954 954 954 954 954 954 672 200 200 37 16 
2500 2500 1040 1040 954 954 954 954 954 954 954 954 676 200 200 37 12 
total count: 13
duration: 1ms

13 вариантов разменять по 17 купюр.
Время работы - 1 миллисекунда. С выводом в файл. С выводом в консоль получается 20мс (очень уж на винде консоль тормозная)

А что у вас?

vadimr Nov 22 2024 at 22:07

Ваш вариант, конечно, в данном случае будет намного быстрее.

wataru Nov 22 2024 at 22:09

А можете ли вы придумать случай, где ваш будет быстрее? (учтите только, что тривиальную оптимизацию выбрасывать лишние купюры из входных данных я прикручу).

vadimr Nov 22 2024 at 22:16

Если с двух сторон прикручивать оптимизации, то программа на C++, конечно, будет быстрее всегда.

Сам по себе метод расчёта матрицы нарастающих итогов очень эффективен, и если его допилить эвристиками, то он прекрасно работает.

wataru Nov 22 2024 at 22:23

то программа на C++, конечно, будет быстрее всегда.

Если программа на С++ в сотни-тысячи раз быстрее чего-то другого, то это не С++ виноват, это более эффективный алгоритм. Можете его хоть на питоне писать - будет быстрее.

Сам по себе метод расчёта матрицы нарастающих итогов

Это вы про динамическое программирование? Да, это эффективный метод, имено это я и утверждаю. Эта задача очень известная и даже ваша модификация (вывести все оптимальные ответы) не меняет ее особо. И широко признаный метод динамического программирования тут работает лучше всего (покуда числа не очень большие. В противном случае все методы работают одинаково плохо). О нем даже в википедии про эту задачу написано.

vadimr Nov 22 2024 at 22:26

Метод динамического программирования не обязательно сводится к расчёту матрицы.

Странно, что вы мне приводите ссылку на Википедию из моей же статьи.

И я вам показал, что одной только матрицей тут не всегда можно обойтись.

wataru Nov 22 2024 at 22:36

Что вы имеете ввиду?

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

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

Еще иногда можно сэкономить на матрице и хранить ее строку или вообще отдельные элементы, но там все еще идет рассчет элементов этой самой "матрицы".

Так что это ваше утверждение скорее ложно, а в лучшем случае - придирка к определениям.

vadimr Nov 22 2024 at 22:41

Динамическое программирование в общепринятом понимании - это просто некоторый индуктивный механизм продукционного вывода. Он может и вообще не иметь численного приложения.

То, о чём вы говорите - это конкретные численные алгоритмы, построенные по методу ДП.

wataru Nov 22 2024 at 22:53

И какое это имеет отношение к обсуждаемой теме? А может и иметь приложение. Вот к этой конкретной задаче он применим и дает вот этот конкретный алгоритм. Который называют ДП.

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

И везде, где этот метод применяют для решения задачи появляется та самая "матрица" о которой вы говорите, ибо в методе ДП предусмотрено переиспользование решений подзадач.

Странно, что вы мне приводите ссылку на Википедию из моей же статьи.

Странно, что вы приведя эту ссылку, пропустили там целую секцию.

И я вам показал, что одной только матрицей тут не всегда можно обойтись.

Я обошелся. И быстрее вашего решения на порядки.

vadimr Nov 22 2024 at 23:05

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

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

wataru Nov 20 2024 at 16:31

Легко доказать, что уменьшение суммы к выдаче на величину универсальной суммы не меняет решение нашей задачи для остатка.

Не правда.

Номиналы {2,3}, надо набрать 7. "Универсальная сумма" - 6. Но остаток 1 вы вообще никак не наберете.

Очевидно, что есть какая-то сумма начиная с которой можно выкинуть НОК. Но ее размер не очевиден. Вот простая оценка сверху:

$\sum_{a \in A} (S-a)+1$

где A - множество всех ноимналов, S - наименьшее общее кратное, ваша "универсальная сумма).

Потому что начиная с этого числа в любом наборе обязательно где-то наберется S одним номиналом, ведь оно больше максимального, которого можно набрать без полного размена S одним номиналом. Для примера выше это будет 4+3+1=8. В вашем примере с купюрами это будет 50200.

Есть подозрение, что это верно начиная с 2S, но я доказательство вывести не смог.

vadimr Nov 20 2024 at 16:41

О том, что, выкидывание НОК само по себе может привести нас в тупик, я не подумал.

Единица – это чтобы строгое больше заменить нестрогим больше или равно?

lightln2 Nov 21 2024 at 16:39

Кажется, что это не верно для 2S, а ваша оценка точная. Например, для набора (6, 22, 33, 66): S=66, 2S=132, sum(S-a)+1 = 138. Но 106 + 222 + 33 = 137 больше 2S, но его нельзя представить с номиналом 66.

wataru Nov 21 2024 at 16:49

Отличный контр-пример!

wataru Nov 20 2024 at 16:32

Код на этом языке программирования большинству читателей вообще не понятен. Какой-нибудь псевдокод был бы лучше в статье.

GlukKazan Nov 20 2024 at 17:25

Поскольку в статье затронуты некоторые нетривиальные моменты, такой псевдокод будет эквивалентен Лиспу

wataru Nov 20 2024 at 17:27

Эквивалентен, да, но понятен гораздо больше.

vadimr Nov 20 2024 at 17:32

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

Что же касается Вашей оценки универсальной суммы, то вставил её в программу.

GlukKazan Nov 20 2024 at 19:08

Ну вот смотрите: статья про недетерминированное программирование, значит в псевдокод придётся ввести amb-оператор. Будет ли такой код сильно понятнее читателю из-за отсутствия скобок? Не уверен.

wataru Nov 20 2024 at 19:45

Достаточно и random. Со скобками, кто с ними не работал, вообще не понятно, с какой стороны это читать. Что тут функции, в какой последовательности и что выполняется.

vadimr Nov 20 2024 at 19:55

Тут всё функции :)

random выдаёт только одно какое-то значение, которое и используется дальше в программе. amb выдаёт все значения одновременно разным инстансам программы, сам эти инстансы и порождая.

wataru Nov 20 2024 at 20:30

А, т.е. это "недетерминированное" программирование - это просто полный перебор? Тут даже рандома не надо, просто рекурсия.

GlukKazan Nov 20 2024 at 20:38

Перебор с отсечением, спрятанный за удобной абстракцией. Рекурсивное решение будет в три раза больше по размеру и во столько же раз непонятнее.

wataru Nov 20 2024 at 21:04

Edit: не на тот коммент ответил сначала.

не знакомым с языком Scheme рекурсивное решение было бы на порядке понятнее. Потом, в псевдокоде можно писать весьма компактно.

vadimr Nov 20 2024 at 21:14

Статья про методы программирования. А задача используется как пример их применения. Поскольку она находится в том числе в хабе Lisp, то быть написанной на диалекте Лиспа для неё нормально :)

GlukKazan Nov 20 2024 at 21:27

напишите, сравним

GlukKazan Nov 20 2024 at 20:08

и чем вам поможет random?

nio-kun Nov 20 2024 at 16:37

Такие задачи хорошо решаются симплекс-методом. Есть очень хорошая книга на эту тему: "Исследование операций" Хэмди А. Таха.

vadimr Nov 20 2024 at 16:39

Что нам здесь даст симплекс-метод?

nio-kun Nov 21 2024 at 12:06

Это ведь стандартная задача на оптимизацию, очень похожая на задачу о рационе. Есть потребность в N чего-нибудь и m видов ресурсов, каждый из которых даёт n этого чего-нибудь и стоит k рублей. Для удовлетворения потребности нужно подобрать такое сочетание количеств каждого ресурса, которое даст в сумме N нужного и будет стоить дешевле всего. В нашем случае k будет у всех ресурсов единица. Строим систему уравнений, прогоняем симплекс-метод и готово - получим близкое к оптимальному решение.

vadimr Nov 21 2024 at 12:28

Субоптимальное решение получить очень легко. Фактически жадный алгоритм и является некоторым частным случаем симплекс-метода. Но в точности решить задачу так, как она здесь поставлена - совсем другое дело.

malkovsky Nov 22 2024 at 12:03

Если ресурс делим на произвольные доли, то это задача линейного программирования и, соответственно, решается симплекс методом. Если же ресурс делится только на какие-то куски, то это задача целочисленного линейного программирования, где хорошего универсального решателя нет, по крайней мере сиплекс-метод таким не является.

Эквивалентом описанной в статье задачи с произвольным делением было бы что-то такое: "Есть несколько порошков с разной удельной стоимостью, нужно отмерить ровно M минимальным возможным объемом". Такая задача решается симплекс-методом, но при этом решается и простым жадным алгоритмом "берем порошок с наибольшей удельной стоимостью пока не закончился, если еще не отмерили -- переходим к следующему порошку"

Anonimeba Nov 20 2024 at 16:47

Так вот почему в Сбербанке больше 100к за раз не выдает :D

botyaslonim Nov 22 2024 at 15:59

В Сбертехе решили усовершенствовать жадный алгоритм и придумали Слишком жадный алгоритм

Duxlab Nov 20 2024 at 17:12

Имхо: поскольку жадный алгоритм, хоть и не идеален, но близок к результату, его можно докостылить до практически пригодного, задав условие: если набор мелких купюр оказывается больше или равен половине более крупной купюры, вычесть сначала такую купюру и повторить.
6000 → 5000+100х10, т.к. 100х10 = 2000/2, то 6000-2000=4000, которые продолжаем выдавать возможными купюрами по тому же принципу.

>6249 при помощи "купюр" номиналами 83, 186, 408 и 419
Ну тут сам себе злой буратина :)
За решение этой задачи в общем виде есть какой-то грант?

п.с. ссылка на вики неправильная.

vadimr Nov 20 2024 at 17:21

Спасибо, ссылку на википедию поправил.

Что касается жадного алгоритма, то он вообще будет ехать не в ту степь при определённых номиналах купюр. Но учитывая, что реальные номиналы купюр обладают удобными для размена свойствами, то я думаю, что в настоящих банкоматах используется какая-то вариация жадного алгоритма. Да и нет у банкомата задачи непременно выдать минимальное количество банкнот.

Mingun Nov 20 2024 at 17:37

Думаю, стоит отметить, что этими удобными свойствами являются кратность номиналов друг другу. Это позволяет заменять купюру одного номинала на несколько купюр меньшего, что меняет раскладку локально, только увеличивая общее количество купюр. При этом для случая неограниченного общего количества купюр в решении есть гарантия, что выдать удастся всегда, если сумма кратна наименьшему номиналу. Если же количество купюр ограничено, то появляется потолок суммы, выше которого не выдать.

Благодарю за пример с 6000 по 3x2000, теперь я понимаю, почему в нашем продукте в алгоритме есть шаг тасовки после набора суммы (проход по всему набору с попыткой заменить купюру на несколько соседних и еще какие-то, но там так заморочено, что я не разбирался). Точнее, было понятно, зачем он, и раньше, но не думал, что он может быть полезен и при стратегии "Крупными купюрами" (т.е. сначала наибольшим номиналом, потом чуть поменьше и т.п.). Надо будет проверить, справится ли он с такой задачей.

Moog_Prodigy Nov 20 2024 at 18:24

У реальных банкоматов обычно встречал не потолок суммы, а запрет на выдачу, если сумма не укладывается в доступные номиналы. Например: 6450. Выдает - 5000 + 1000 + 400 + "ой а полтинники уже давно в банкоматы не кладут". Ошибка. Введите сумму кратную 100. И всегда от большего к меньшему считают. 8700 = 5000 + 2000+ 1000 + 500 + 100 + 100. Если какие то купюры кончились. например 1000, он будет стараться выдавать не по 100 а по 500. В итоге купюр уйдет больше, но банкомат выполнит свою задачу.

Mingun Nov 20 2024 at 19:10

Потолок естественным образом получается по остатку в кассетах и общей пропускной способности в щели выдачи. Хотя можно с ним и не встречаться никогда. В старых диспенсерах в щель пролезает 40 купюр (для рублей это примерно 1 см.), а в современных ресайклерах больше 100. Купюр в кассеты загружают по разному, но можно считать, что около 1000-2000 будет. Даже если максимальный номинал 1000, потолок будет 100 тысяч, что не каждый день снимают.

Жадный алгоритм тоже не всегда нравится банкам, т.к. он опустошает крупные купюры быстро, т.к. в местах установки банкоматов многие снимают зарплату. Обычно есть желание разбавлять крупные купюрами несколькими мелкими. В некоторых странах даже законы есть, что как минимум одна мелкая должна быть в выдаче, хотя там обратная проблема -- часто просят мелкий номинал и он быстрее всех уходит (потому и закон, чтобы не оптимизировали вопреки желанию граждан).

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

vadimr Nov 20 2024 at 19:15

Очень интересный комментарий. Не думал про таблицы! А ведь действительно, готовый список ответов может оказаться самым эффективным решением и по времени, и по памяти.

xSVPx Nov 20 2024 at 22:41

Но ведь банкомат знает сколько у него купюр осталось и может для каждой выдачи подобрать такую комбинацию, чтобы остаток был наиболее "удачным". Какой смысл в таблицах ?

vvbob Nov 21 2024 at 11:06

В банкоматах некоторых банков есть в меню опция - выдать по возможности крупными/мелкими купюрами.

HardWrMan Nov 21 2024 at 11:52

Помимо заготовок появился и явный выбор доступных купюр:

Alexandroppolus Nov 20 2024 at 17:25

Жадный алгоритм с возвратами (увы, не всегда разменивающий оптимально) можно запилить на регулярках и унарной записи числа.

const func = (n, a) => '1'.repeat(n).match(`^((?:.{${a.join('})*)((?:.{')}})*)$`)
    ?.slice(1).map((s,i)=>s.length/a[i]);

// пример
console.log(func(143, [34, 19, 9, 4])); // количества монет: [3, 1, 2, 1]

На скорость этот вариант не претендует, чисто по фану.

upd: чуть упростил. Сегодня я узнал, что match умеет сделать регулярку из строки )

insecto Nov 24 2024 at 06:23

я ща полицию вызову

HardWrMan Nov 20 2024 at 17:38

А как быть с модификаторами алгоритма? Например, стремление банка равномерно опустошать кассеты понятно, но вот клиенту хочется крупными или наоборот мелкими? Ну вот как тут, например:

В наших банкоматах ещё есть кнопочки "мелкими" и "равномерно".

vadimr Nov 20 2024 at 17:43

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

Но повторюсь, что реальный банкомат не ставит перед собой задачу найти математически лучшее решение.

HardWrMan Nov 20 2024 at 18:05

Но повторюсь, что реальный банкомат не ставит перед собой задачу найти математически лучшее решение.

Как работают банкоматы я знаю не по наслышке. Как правило, у него конкретный набор алгоритмов, из которых выбирает пользователь (я помню время, когда выбора не было и как он стал появляться), который опирается на внутренние номиналы и счётчики листов в кассетах. Количество листов в кассете и их номинал задаётся кассиром при инкассации. Помню, была ошибка, когда 10к листы пометили как 1к. Была большая буча и экстренная инкассация этого банкомата. И расследование. Благо, ущерб был не сильный и его удалось локализовать после анализов логов, у успевших снять даже овердрафта не случилось.

axion-1 Nov 20 2024 at 17:42

Задача на динамическое программирование, действительно medium сложности. Ничего крайне сложного в ней нет. На leetcode же не требуется анализировать все возможные решения и находить строго оптимальное.

vadimr Nov 20 2024 at 17:47

Отчасти согласен с Вами, но я не понимаю, как они предполагают укладываться в лимит времени (какой он там, кстати?) в сложных случаях. Или там не любые значения предлагаются к решению (о чём ничего не сказано в условиях), или результат зависит от игры случая при выборе номиналов. Мне сложно представить, как простым алгоритмом получить решение для тех же самых 6249 и (83 186 408 419) за разумное время.

axion-1 Nov 20 2024 at 18:02

Если правильно помню, там для каждой задачи заданный набор тест кейсов, программа должна на них выдать правильные результаты и уложиться в лимит по времени.

wataru Nov 20 2024 at 18:07

Там ограничение на максимальную сумму и количество номиналов, и поэтому работает очень быстро. И решается задача динамическим программированием, но не таким, как указал автор. Автор ищет все кратчайшие варинты набрать все возможные суммы за ровно k монет и через них высчитывает для k+1, а надо считать минимальное количество монет, чтобы набрать сумму X. Такое ДП работает за O(NS), что для ограничений в задаче N=12, S=10000 отрабатывает моментально.

vadimr Nov 20 2024 at 18:16

Я понял. Получается, что они не ставят задачу найти все решения. Тогда дело, конечно, радикально упрощается.

vadimr Nov 21 2024 at 00:27

Что-то я не учёл ещё, что в приведённом примере всего 4 номинала. Показанное в статье ДП тоже работает очень быстро в таком случае и выдаёт единственное решение.

Но для 12 номиналов найти все решения очень сложно.

wataru Nov 21 2024 at 12:09

Да нет, с тем же ДП по набираемой сумме можно устроить полный перебор, который нигде не зайдет в тупик. В итоге время работы будет O(NS+A), где A - размер ответа. Да, он экспоненциальный, основание зависит от N и собственно номиналов, а степень от искомой суммы S. Я бы назвал это простым решением и максимально быстрым (насколько решение такой задачи вообще может быть быстрым).

vadimr Nov 21 2024 at 12:23

Если мы делаем полный перебор, то нет существенной разницы, в каком порядке его делать. В переборе по количеству шагов мы будем отсекаться по превышению суммы, а в переборе по сумме - отсекаться по количеству шагов (которое, в отличие от суммы, нам априорно неизвестно). Но всё равно в общем случае (а особенно когда решений нет) нам надо перебрать все комбинации для меньших сумм.

wataru Nov 21 2024 at 12:43

Я в соседней ветке привел код. Дело в том, что мы знаем количество шагов! его элементарно можно найти за O(NS) динамическим программированием.

vadimr Nov 21 2024 at 13:09

Справедливое замечание.

wataru Nov 20 2024 at 18:12

Стоит еще отметить, что в статье указано динамическое программирование, но не то, которое обычно имеют ввиду при решении этой задачи и ждут на leetcode. В стандартном ДП вы считаете минимальное количество монет, чтобы набрать данную сумму. Алгоритм в статье же считает все возможные суммы, которые можно набрать используя k монет.

Стандартное ДП работает очень быстро, если искомая сумма относительно небольшая. Большую же можно свести к небольшой используя описанный в статье прием с "универсальной суммой".

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

adel-s Nov 20 2024 at 19:28

Ох... а ведь эта задача была у меня на школьной городской олимпиаде по программированию. И решал я её тогда именно жадным алгоритмом.
Наверное, поэтому, и не прошёл дальше :)

HardWrMan Nov 20 2024 at 23:19

Когда я случайно попал в школе на олимпиаду, там был вопрос типа "можно ли набрать сумму Х имея набор из монет A, B и C?".

Dhwtj Nov 21 2024 at 08:39

Мне это напомнило задачу автоматического подбора ширины и высоты ячеек таблиц (HTML, Excel и т.п.) в зависимости от их содержимого. Еще бы учесть, что часть ячеек объединена, а часть с вертикальным текстом.

Задача формулируется просто, но нечетко. А так как человеку свойственно "я делал это много раз", "и так сойдет", то четкой формулировки добиться трудно. А при четкой формулировке длина постановки задачи вырастет в десятки а может и сотни раз в сравнении с исходной формулировкой. А алгоритм его решения и еще больше.

Такая вот скрытая сложность задачи.

vadimr Nov 21 2024 at 08:41

Да, совершенно верно. Это всё варианты математической задаче об упаковке рюкзака.

a0m55 Nov 21 2024 at 10:12

Так, например, полное решение для номиналов (83 186 408 419 417 421 423 425 427 429 431 477) и суммы 6249 найти в обозримое время не представляется возможным, хотя оно существует (первые 4 из этих номиналов позволяют сформировать выдачу из 20 купюр)

Быстро нашлось решение 19 купюрами:

3*477 + 1*431 + 1*429 + 1*427 + 1*425 + 1*423 + 1*421 + 1*419 + 2*417 + 1*408 + 1*186 + 5*83

vadimr Nov 21 2024 at 10:12

Но без доказательства единственности?

wataru Nov 21 2024 at 12:40

Ниже код полного перебора, который работает моментально и находит решение через 14 купюр (155 вариантов).

wataru Nov 21 2024 at 12:39

Вообще, для такой маленькой суммы решение работает за миллисекунды и находит следующие решия длины 14:

155 решений

Полный перебор с оптимизацией через ДП

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int S = 6249;
const int N = 12;
const int a[N] = {83, 186, 408, 419, 417, 421, 423, 425, 427, 429, 431, 477};
// dp[i][j] = минимальное количество купюр среди первых i номиналов, чтобы набрать сумму j.
int dp[N+1][S+1];

int total_count = 0;

void PrintAll(int s, int n, vector<int> &coins) {
    if (s == 0) {
        for (size_t i = 0; i < coins.size(); ++i) {
            cout << coins[i] << " ";
        }
        cout << "\n";
        ++total_count;
        return;
    }
    // Пробуем не брать максимальную купюру вообще.
    if (n > 0 && dp[n-1][s] == dp[n][s]) PrintAll(s, n-1, coins);
    // Пробуем взять максимальную купюру один раз.
    if (s >= a[n-1] && dp[n][s-a[n-1]] == dp[n][s]-1) {
        coins.push_back(a[n-1]);
        PrintAll(s-a[n-1], n, coins);
        coins.pop_back();
    }
}

int main() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= S; ++j) {
            // всегда можно просто не брать максимальную купюру.
            dp[i][j] = dp[i-1][j];
            if (j < a[i-1]) {
                continue;
            }
            int prev = dp[i][j-a[i-1]];
            // если берем максимальную купюру, то только если через нее короче.
            if (prev != -1 && (dp[i][j] == -1 || dp[i][j] > prev + 1)) {
                dp[i][j] = prev + 1;
            }
        }
    }
    
    cout << "lenth: " << dp[N][S] << "\n";
    
    vector<int> solution;
    PrintAll(S, N, solution);
    cout << "total count: " << total_count << "\n";
    return 0;
}

vadimr Nov 21 2024 at 13:08

Да, действительно удалось существенно ускорить за счёт компиляции и обрезания ненужных ветвей массивом dp! В реальной жизни, конечно, будет не настолько быстро, потому что размер массива заранее неизвестен, но всё равно быстро.

wataru Nov 21 2024 at 13:14

В смысле, неизвестен? Пользователь попросил разменять 100500 рублей - это и есть размер массива.

vadimr Nov 21 2024 at 13:17

Я имею в виду, что у вас это забито в константы в тексте программы, на что ориентируется компилятор при генерации кода для доступа к матрице. При динамическом размере массива будет считаться несколько медленнее. Но это всё копейки.

wataru Nov 21 2024 at 13:24

Ну это для простоты примера. Можно же динамически выделять память в каком-нибудь vector. И его можно точно также сделать плоским, что индексация будет все также простой (одномерный вектор, считать смещения руками).

vadimr Nov 21 2024 at 13:27

Да, всё верно, но это заметно влияет на производительность, особенно в архитектуре Intel. Хотя для тех вещей, о которых мы говорим, конечно, разница даже в 2-3 раза неважна.

wataru Nov 21 2024 at 13:51

Ну вы не правы, там машинный код идентичный вообще получается с любыми настройками оптимизации.

Edit: ну хорошо, чуть-чуть разный код, но эквивалентный. Другие имена регистров, чуть подругому развернут цикл на высоком уровне оптимизации, но, собственно, индексация и доступ к памяти точно такие же.

vadimr Nov 21 2024 at 14:28

Если вы во второй пример вместо константы 1000 подставите параметр N, код существенно изменится.

wataru Nov 21 2024 at 14:37

Нет. Индексация не изменится. Да, при высоком уровне оптимизации с константой цикл разворачивается и векторизуется. Но это не к индексации и доступу к матрице.

vadimr Nov 22 2024 at 10:48

Векторизация цикла – это и есть код для доступа к матрице.

StjarnornasFred Nov 21 2024 at 11:27

А как насчёт последовательного применения жадных алгоритмов, причём каждый следующий раз мы исключаем из рассмотрения наибольшую купюру?

Например, для 6400 рублей и стандартного набора купюр получаем:

5000 + 1000 + 200 + 200 = 4
2000 + 2000 + 2000 + 200 + 200 =5
1000 + 1000... и т.д., в итоге проходим все значения и выбираем из них наименьшее, в данном случае 4.

vadimr Nov 21 2024 at 11:34

Попробуйте так разменять 11000 в наборе (5000, 2000, 100).

В общем случае рассмотренная задача экспоненциально сложна, у неё нет эффективного решения.

StjarnornasFred Nov 22 2024 at 00:44

Ок, тогда усовершенствую идею. Последовательность жадных алгоритмов, каждый последующий берёт на 1 меньше (вплоть до 0) купюр крупнейшего номинала. Во избежание лишних проверок: если сумма равна любой купюре или делится нацело на крупнейшие - сразу останавливать расчёт.

vadimr Nov 22 2024 at 10:02

Проблема у нас может возникнуть на любой купюре, кроме самой младшей. Поэтому такая последовательность будет полным перебором.

DanisGB Nov 21 2024 at 13:13

Так, например, полное решение для номиналов (83 186 408 419 417 421 423 425 427 429 431 477) и суммы 6249 найти в обозримое время не представляется возможным, хотя оно существует

ну... написал небольшой код на python: 131 комбинация из 17 купюр, где каждая присутствует минимум 1 раз, к примеру: 2*83 + 1*186 + 3*408 + 2*419 + 1*417 + 1*421 + 1*423 + 1*425 + 1*427 + 1*429 + 3*431.

155 комбинаций из 14 купюр, много нулевых членов: 0*83 + 0*186 + 1*408 + 1*419 + 1*417 + 0*421 + 0*423 + 1*425 + 1*427 + 1*429 + 2*431 + 6*477 == 1*408 + 1*419 + 1*417 + 1*425 + 1*427 + 1*429 + 2*431 + 6*477

0*83 + 1*186 + 2*408 + 0*419 + 0*417 + 0*421 + 0*423 + 0*425 + 0*427 + 0*429 + 0*431 + 11*477 == 1*186 + 2*408 + 11*477

StjarnornasFred Nov 22 2024 at 16:08

Человек каким-то образом решает эту задачу за секунды (если не брать в расчёт "хитромудрые" вымышленные наборы купюр по 425 и 186 рублей). Может, имеет смысл решать её не алгоритмически, а с помощью нейросети? Или попробовать понять, каким образом её решает человек.

vadimr Nov 22 2024 at 16:12

Человек решает жадным алгоритмом и не ставит перед собой цель найти наилучшее решение.

wataru Nov 22 2024 at 20:25

Человек каким-то образом решает эту задачу за секунды

Я выше привел алгоритм, который решает ее для этих чисел за миллисекунды. Это широко известная задача размена монет, на википедии даже алгоритм решения приведен.

andnotor Nov 24 2024 at 14:08

А в чем смысл использования языка программирования который потом на практике не используется?

vadimr Nov 24 2024 at 14:28

https://habr.com/ru/articles/856508/

В том, чтобы для начала разобраться с теорией.

andnotor Nov 26 2024 at 12:02

Посмотрел на него, спасибо, но так и не понял в чем суть... Ну и ладно :) :) Просто в свое время нас учили pascal который и тогда был менее используемым чем C. И обоснование было тоже мол простой для начала. 🤦🤷 Так что останусь при своем мнении, что учиться надо на том что будешь использовать в будущем.

vadimr Nov 26 2024 at 12:35

Из первых пяти языков программирования, которые я выучил 35 лет назад, в настоящее время используется только Фортран, да и то редко и изменившись до неузнаваемости. Это вообще не тот вопрос, о котором надо беспокоиться. Учили бы вы Си, он бы сейчас вам в том виде тоже ничем не помог бы, а только голову бы задурил.

За 10 лет стек технологий обновляется существенно для пересмотра, а за 20 - практически полностью.

andnotor Nov 26 2024 at 18:13

Хм... Главное не говорить моему Delphi :) :) который служит (в современном виде конечно) мне и сейчас. JS, HTML, Java, Python и тот же C я бы не сказал, что диаметрально куда то развернулись. А кардинально менять стек конечно можно и каждый год если деньги есть, но это же больше про библиотеки и фреймворки ;)

HardWrMan Nov 26 2024 at 18:49

Программисты на Delphi (точнее, объектном паскале) они как члены Бойцовского Клуба. А первое правило Бойцовского Клуба никогда не говорить про Бойцовский Клуб! *подмигиваю со значением*

andnotor Nov 29 2024 at 19:21

Я тебя понял Бро 😉