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

Question

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

Например, предположим, что конверт может содержать только три печати, а доступные значения марок: 1 цент, 2 цента, 5 центов и 20 центов.Тогда решение составляет 13 центов;поскольку любое меньшее значение может быть получено максимум с тремя марками (например, 4 = 2 + 2, 8 = 5 + 2 + 1 и т. д.), но для получения 13 центов необходимо использовать как минимум четыре марки.

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

Другой пример:
Максимум 5можно использовать штампы
Значение: 1, 4, 12, 21
Наименьшее значение, которое не может быть достигнуто, равно 72. Значения 1-71 могут быть созданы с определенной комбинацией.

В концеЯ, вероятно, буду использовать Java для кодирования этого.

Answer 1

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

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

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

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

Answer 2

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

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

• A 1 к набору марок, добавив до 82-1 = 81, либо
• A 2 к набору марок, добавивдо 82-2 = 80, или
• A 7 для набора марок, добавив до 82-7 = 75, или
• A 12 для набора марок, добавив до 82-12 = 70, или
• A 50 к набору марок, суммирующих до 82-50 = 32.

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

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

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

Answer 3

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

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

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

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

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

Answer 4

        import java.util.ArrayList;
        import java.util.List;
        /**
         * 
         * @author Anandh
         *
         */
        public class MinimumStamp {

            /**
             * @param args
             */
            public static void main(String[] args) {
                // TODO Auto-generated method stub
                int stamps[]={90,30,24,15,12,10,5,3,2,1};
                int stampAmount = 70;
                List<Integer> stampList = minimumStamp(stamps, stampAmount);
                System.out.println("Minimum no.of stamps required-->"+stampList.size());    
                System.out.println("Stamp List-->"+minimumStamp(stamps, stampAmount));  
            }

            public static List<Integer> minimumStamp(int[] stamps, int totalStampAmount){
                List<Integer> stampList =  new ArrayList<Integer>();
                int sumOfStamps = 0;
                int remainingStampAmount = 0;
                for (int currentStampAmount : stamps) {
                    remainingStampAmount = totalStampAmount-sumOfStamps;
                    if(remainingStampAmount%currentStampAmount == 0){
                        int howMany = remainingStampAmount / currentStampAmount;
                        while(howMany>0){
                            stampList.add(currentStampAmount);
                            howMany--;
                        }
                        break;
                    }else if(totalStampAmount == (sumOfStamps+currentStampAmount)){
                        stampList.add(currentStampAmount);
                        break;
                    }else if(totalStampAmount > (sumOfStamps+currentStampAmount) ){
                        int howMany = remainingStampAmount / currentStampAmount;
                        if(howMany>0){
                            while(howMany>0){
                                stampList.add(currentStampAmount);
                                sumOfStamps += currentStampAmount;
                                howMany--;
                            }
                        }else{
                            stampList.add(currentStampAmount);
                            sumOfStamps += currentStampAmount;
                        }
                    }
                }
                return stampList;
            }
        }

Answer 5

Может быть, немного бесполезно просто давать «подсказки» о решении 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.) Скомпилированный язык будет еще быстрее.