9

切手問題は、手紙が限られた数の切手をしか保持できず、これらが特定の特定の額面値しか持たない場合に、封筒に入れることができない最小の切手値を尋ねる数学的な謎です。

たとえば、封筒に入れることができるスタンプは3つだけで、使用可能なスタンプの値は1セント、2セント、5セント、および20セントであるとします。その場合、解決策は13セントです。最大で3つのスタンプ（たとえば、4 = 2 + 2、8 = 5 + 2 + 1など）でより小さな値を取得できますが、13セントを取得するには、少なくとも4つのスタンプを使用する必要があります。

許可される切手の最大量と切手の額面を考慮して、封筒に入れることができない最小の切手を見つけることができるアルゴリズムはありますか？

別の例：
最大5つのスタンプを使用できます値
：1、4、12、21
到達できない最小値は72です。値1〜71は、特定の組み合わせで作成できます。

結局、私はおそらくこれをコーディングするためにJavaを使用するでしょう。

4

5 に答える 5

3

スタンプのすべての可能な組み合わせの合計を（おそらく再帰によって）徹底的に計算するのではなく、すべての可能な合計を検討し、各合計を生成するためのスタンプの最小数を計算します。スタンプの組み合わせはたくさんありますが、明確な合計ははるかに少ないです。

コメントで示した例では、10個のスタンプが封筒に収まり、100を超える値のスタンプはありません。スタンプn^10の組み合わせがあります。ここnで、は使用可能なスタンプの額面の数です。しかし、10個のスタンプの可能な最大の合計はわずか1000です。1001までの配列を作成し、これらすべての値について、それぞれを作成するために必要なスタンプの最小数を計算する効率的な方法を考えてみてください。あなたの答えは、11（またはそれ以上）のスタンプを必要とする最小のインデックスであり、各スタンプカウントを11に制限することもできます。

この場合の「効率的」とは、基本的に「必要のない作業を繰り返さないこと」を意味します。したがって、中間結果を可能な限り再利用する必要があります。

それがヒントとして十分でない場合は、（a）アプローチについて間違っている（この場合、申し訳ありませんが、答える前に実際に問題を自分で解決していません）、または（b）更新してどこまで進んだかを伝えますそれらの線に沿って。

于 2010-09-30T01:51:07.683 に答える
3

はい、そのようなアルゴリズムがあります。素朴に：1から始めて、合計が1になる組み合わせが見つかるまで、可能なすべてのスタンプの組み合わせを試し、次に2を試します。スタンプの組み合わせがその数に追加されないような数が見つかると、アルゴリズムは終了します。

おそらく遅いですが、十分に小さい問題（たとえば、100スタンプ、10ポジション）の場合、「合理的な」時間でこれを解決できます...

しかし、大きな問題、たとえば多くのスタンプが利用可能であり（たとえば、1000）、多くの可能な位置（たとえば、1000）がある場合、このアルゴリズムは手に負えないほどの時間がかかる可能性があります。つまり、非常に大きな問題の場合、このアプローチを使用して問題を解決する時間は、たとえば宇宙の寿命である可能性があり、したがって、それはあなたにとって実際には役に立ちません。

検索を高速化する方法を見つける必要がある非常に大きな問題がある場合、これらの高速化はヒューリスティックと呼ばれます。問題を克服することはできませんが、ある種のドメイン知識を適用することで、単純なアプローチよりも早く問題を解決できる可能性があります。

この素朴なアプローチを改善する簡単な方法は、探している数と等しくないスタンプの組み合わせを試すときはいつでも、将来の数を試すために可能なセットからその組み合わせを削除し、その未来をマークすることです。利用できない番号。別の言い方をすれば、すでに見つけた数字とそこにたどり着いた組み合わせのリストを保持し、それらの数字やそれらの組み合わせを再度探す必要はありません。

于 2010-09-30T01:42:21.143 に答える
3

別のヒントを次に示します。ある数になるスタンプのすべてのセットは、合計がその数より少ない最小サイズのスタンプセットに1つのスタンプを追加することによって形成できます。

たとえば、スタンプ1、2、7、12、および50があり、スタンプが5つに制限されていて、82を表現できるかどうかを調べたいとします。その82を取得するには、次のいずれかを追加する必要があります。

  • 1から82-1=81までのスタンプのセット、または
  • 合計82-2=80のスタンプのセットに2、または
  • 合計82-7=75のスタンプのセットに7、または
  • 合計82-12=70のスタンプのセットに12、または
  • 合計82-50=32のスタンプのセットに50。

これらは、82を形成できる唯一の可能な方法です。 これらの5つの可能性すべての中で、1つ（またはおそらく複数）のスタンプの数が最小になります。その最小数が5より大きい場合、82をスタンプで表すことはできません。

また、数値を表すことができる場合は、より大きな数値の計算で使用できるように、それに必要な最小数のスタンプを記録する必要があることにも注意してください。

これに加えて、Steve Jessopの答えがあれば、動的計画法ソリューションの正しい方向に進むことができれば幸いです...それでも困っている場合は、お知らせください。

于 2010-09-30T04:55:22.253 に答える
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配列を直接使用して、より小さな問題サイズの答えを得ることができます。

スタンプサイズ1、4、12、21、封筒サイズ1000の場合を解決するには、PCで93ミリ秒かかります（答えは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 に答える