信封上邮票的最大值

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

是的，有这样的算法。天真地：从 1 开始，尝试所有可能的邮票组合，直到找到总和为 1 的组合，然后尝试 2，依此类推。当您的算法找到一个数字并且没有任何邮票组合可以添加到该数字时，您的算法就完成了。

尽管可能很慢，但对于足够小的问题（比如 100 个邮票，10 个位置），您可以在“合理”的时间内解决这个问题......

但是，对于大问题，我们有很多可用邮票（比如 1000 个）和很多可能的位置（例如 1000 秒），该算法可能会花费大量时间。也就是说，对于非常大的问题，使用这种方法解决问题的时间可能是宇宙的寿命，因此它对您来说并不是真正有用。

如果您有非常大的问题，您需要找到加速搜索的方法，这些加速称为启发式。你无法解决问题，但通过应用某种领域知识，你可能可以比简单的方法更快地解决问题。

改进这种天真的方法的一个简单方法可能是，每当您尝试不等于您要查找的数字的邮票组合时，您都会从可能的集合中删除该组合以尝试任何未来的数字，并标记该未来号码为不可用。换句话说：保留一个你已经找到的数字和组合的列表，然后不要再次寻找这些数字或它们的组合。

Answer 2

这里还有另一个提示：每组总和达到某个给定数字的邮票都可以通过将 1 个邮票添加到总和小于该数字的最小邮票组中来形成。

例如，假设我们有邮票 1、2、7、12 和 50，并且限制为 5 个邮票，我们想知道是否可以表示 82。要得到 82，您必须添加：

• A 1 到一组总计为 82-1=81 的邮票，或
• A 2 到一组总计为 82-2=80 的邮票，或
• A 7 到一组总计为 82-1=81 的 邮票。邮票加起来为 82-7=75，或
• A 12 为一套邮票加起来为 82-12=70，或
• A 50 为一套邮票加起来为 82-50=32。

这些是形成 82 的唯一可能方式。在所有这 5 种可能性中，一种（或可能不止一种）将具有最少数量的印章。如果该最小数量> 5，那么82就不能用邮票来表示了。

另请注意，如果可以表示一个数字，则需要记录该数字所需的最小标记数，以便计算更大的数字时可以使用它。

加上Steve Jessop的回答，希望能让您明白动态编程解决方案的正确方向...如果您仍然感到困惑，请告诉我。

Answer 3

不要详尽地计算所有可能的邮票组合的总和（可能通过递归），而是考虑所有可能的总和，并计算出产生每个总和的最小邮票数量是多少。邮票的组合有很多，但不同的总和却少得多。

在您在评论中给出的示例中，一个信封适合 10 张邮票，没有一张邮票的价值大于 100。邮票有 n^10 种组合，其中 n是可用邮票的面额数量。但 10 个邮票的最大可能总和仅为 1000。创建一个最多 1001 的数组，并尝试想出一种有效的方法来计算出将所有这些值加在一起，制作每个邮票所需的最少邮票数量。那么您的答案就是需要 11 个（或更多）邮票的最少索引，并且您也可以将每个邮票数量限制为 11 个。

在这种情况下，“高效”基本上意味着“避免重复任何不必要的工作”。因此，您将希望尽可能地重用中间结果。

如果这还不够提示，那么（a）我对方法的理解是错误的（在这种情况下，抱歉，在回答之前我自己实际上还没有解决问题）或（b）更新说明你已经走了多远沿着这些思路。

Answer 4

当有人猜测存在 DP 解决方案时，仅仅给出有关 DP 解决方案的“提示”可能有点无益。所以这里是实现实际 DP 算法的可运行 Perl 代码：

#!/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 数组来获取较小问题的答案。

在我的 PC 上，解决邮票尺寸 1、4、12、21 和信封尺寸 1000 的情况需要 93 毫秒。（答案是 20967。）编译语言会更快。

Answer 5

        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;
            }
        }