9

邮票问题是一个数学谜题，它询问不能放在信封上的最小邮资是多少，如果这封信只能容纳有限数量的邮票，而这些邮票可能只有特定的面值。

例如，假设信封只能装三张邮票，可用的邮票值为 1 美分、2 美分、5 美分和 20 美分。那么解决方案是 13 美分；因为任何较小的值都可以通过最多三个邮票获得（例如 4 = 2 + 2、8 = 5 + 2 + 1 等），但要获得 13 美分，必须至少使用四个邮票。

有没有一种算法，给定允许的最大邮票数量和邮票的面值，可以找到不能放在信封上的最小邮资？

另一个例子：
最多可以使用 5 个印章
值：
1、4、12、21 不能达到的最小值是 72。值 1-71 可以通过某种组合创建。

最后，我可能会使用 Java 来编写代码。

4

5 回答 5

3

这里是另一个提示：加起来等于某个给定数字的每组邮票可以通过将 1 个邮票添加到加起来小于该数字的最小大小的一组邮票来形成。

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

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

这些是形成 82 的唯一可能方式。 在所有这 5 种可能性中，一种（或可能不止一种）的邮票数量最少。如果该最小数字大于 5，则 82 不能用邮票表示。

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

这一点，加上史蒂夫·杰索普的回答，有望让您的思路走上正确的动态编程解决方案……如果您仍然难以理解，请告诉我。

于 2010-09-30T04:55:22.253 回答
3

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

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

但是，对于大问题，我们有很多可用的标记（比如 1000 秒）和许多可能的位置（比如 1000 秒），这个算法可能会花费很多时间。也就是说，对于非常大的问题，使用这种方法解决问题的时间可能是宇宙的生命周期，因此它对你并没有真正的用处。

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

改进这种幼稚方法的一种简单方法可能是，每当您尝试使用不等于您正在寻找的数字的邮票组合时，您从可能的集合中删除该组合以尝试任何未来的数字，并标记那个未来号为不可用。换一种说法：保留一个你已经找到的数字列表以及让你到达那里的组合，然后不要再寻找这些数字或其组合。

于 2010-09-30T01:42:21.143 回答
3

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

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

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

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

于 2010-09-30T01:51:07.683 回答
1

当有人猜测甚至存在一个 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 上需要 93 毫秒来解决邮票尺寸 1、4、12、21 和信封尺寸 1000 的情况。（答案是 20967。）编译语言会更快。

于 2010-09-30T05:49:06.563 回答
1 
        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;
            }
        }
于 2014-06-08T20:31:37.233 回答