Максимальная стоимость почтовых марок на конверте

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

Хотя, возможно, медленно, для достаточно небольших задач (скажем, 100 марок, 10 позиций) вы можете решить это за «разумное» время...

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

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

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

Вот еще один совет: каждый набор марок, который в сумме дает некоторое заданное число, можно сформировать, добавив 1 марку к набору марок минимального размера, который в сумме дает меньше этого числа.

Например, предположим, что у нас есть марки 1, 2, 7, 12 и 50 и ограничение в 5 марок, и мы хотим выяснить, можно ли представить 82 марки. Чтобы получить это 82, вы должны добавить:

• 1 к набору марок в сумме дает 82-1=81, или
• 2 к набору марок в сумме 82-2=80, или
• От 7 к набору марок в сумме получается 82-7=75, или
• 12 к набору марок в сумме дают 82-12=70, или
• 50 к набору марок в сумме дают 82-50=32.

Это единственные возможные способы, которыми можно сформировать 82. Среди всех этих 5 вариантов один (или, возможно, более одного) будет иметь минимальное количество марок. Если это минимальное число > 5, то 82 не могут быть представлены марками.

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

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

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

В примере, который вы привели в комментарии, на конверт помещается 10 марок, и ни одна из марок не имеет номинала больше 100. Существует n^10 комбинаций марок, где n — количество доступных номиналов марок. Но максимально возможная сумма 10 марок — всего 1000. Создайте массив до 1001 и попытайтесь придумать эффективный способ вычислить для всех этих значений вместе наименьшее количество марок, необходимое для изготовления каждой из них. Тогда ваш ответ — это наименьший индекс, требующий 11 (или более) марок, и вы также можете ограничить количество марок до 11.

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

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

Может быть, немного бесполезно просто давать «подсказки» о решении DP, когда есть предположение, что оно вообще существует. Итак, вот исполняемый код Perl, реализующий фактический алгоритм DP:

#!/usr/bin/perl
my ($n, @stamps) = @ARGV;
my @_solved;        # Will grow as necessary

# How many stamps are needed to represent a value of $v cents?
sub solve($) {
    my ($v) = @_;
    my $min = $n + 1;

    return 0 if $v == 0;

    foreach (@stamps) {
        if ($v >= $_) {
            my $try = $_solved[$v - $_] + 1;
            $min = $try if $try < $min;
        }
    }

    $_solved[$v] = $min;
    return $min;
}

my $max = (sort { $a <=> $b } @stamps)[-1];

# Main loop
for (my $i = 0; $i <= $max * $n; ++$i) {
    my $ans = solve($i);
    if ($ans > $n) {
        print "$i cannot be represented with <= $n stamps of values " . join(", ", @stamps) . ".\n";
        last;
    }
}

Обычно solve() требует рекурсивного вызова, но поскольку мы всегда пробуем значения в порядке 0, 1, 2, 3..., мы можем просто использовать массив @_solved напрямую, чтобы получить ответ для задач меньшего размера.

На моем компьютере требуется 93 мс, чтобы решить проблему с размерами марок 1, 4, 12, 21 и размером конверта 1000. (Ответ: 20967.) Компилируемый язык будет еще быстрее.