-4

渡された量が一連の数値から加算的に構築できるかどうかを決定するための非再帰的アルゴリズムとは何ですか。
私の場合、一連の請求書（$ 5、$ 10、$ 20の請求書など）の組み合わせを合計することで、特定の通貨額（$ 40など）を満たすことができるかどうかを判断しています。これは単純な例ですが、アルゴリズムはどの通貨セットでも機能する必要があります（一部の通貨はファンキーな請求額を使用し、一部の請求は特定の時間に利用できない場合があります）。
したがって、$ 50は（$20と$30）のセットで満たすことができますが、（$20と$40）のセットで満たすことはできません。非再帰的要件はSQL Server 2000、再帰のサポートが制限されているターゲットコードベースによるものです。
さらに、これは、利用可能な請求書のセットが変更される可能性がある多通貨環境をサポートするためのものです（たとえば、外国為替窓口係を考えてみてください）。

4

9 に答える 9

3

アルゴリズムを再帰的にすることはできないと 2 度述べましたが、それがこの問題の自然な解決策です。いずれにせよ、この問題を解決するには検索を実行する必要があります。再帰が外れている場合は、手動でバックトラックする必要があります。

目標値を下回る最大の通貨値を選択します。一致していれば完了です。そうでない場合は、現在のターゲット値をスタックにプッシュし、ターゲット値から選択した通貨値を減算します。一致するものが見つかるか、通貨の値がなくなるまで、これを続けます。次に、スタックを使用してバックトラックし、別の値を選択します。

基本的に、これは手動で管理されたスタックを使用したループ内の再帰的なソリューションです。

于 2008-09-15T17:09:08.167 に答える
3

各金種を基数 n の点として扱う場合 (n は必要な音符の最大数)、問題のスペースを使い果たすか解決策が見つかるまで、その数をインクリメントできます。

必要な紙幣の最大数は、必要な合計額を最低額面紙幣で割ったものです。

これは問題に対する強引な対応ですが、間違いなく機能します。

ここにいくつかのpコードがあります。私はおそらくフェンスの支柱でいたるところにいて、ばかげているほど最適化されていませんが、うまくいくはずです。とにかくその考えは正しいと思います。

Denominations = [10,20,50,100]
Required = 570

Denominations = sort(Denominations)
iBase = integer (Required / Denominations[1])

BumpList = array [Denominations.count]
BumpList.Clear

repeat 
    iTotal = 0 
    for iAdd = 1 to Bumplist.size
        iTotal = iTotal + bumplist [iAdd] * Denominations[iAdd]
    loop
    if iTotal = Required then exit true

    //this bit should be like a mileometer. 
    //We add 1 to each wheel, and trip over to the next wheel when it gets to iBase
    finished = true
    for iPos from bumplist.last to bumplist.first 
        if bumplist[iPos] = (iBase-1) then bumplist[iPos] = 0 
        else begin
            finished = false
            bumplist[iPos] = bumplist[iPos]+1
            exit for
        end
     loop 
until (finished)

exit false
于 2008-09-15T17:22:09.790 に答える
2

これは、動的計画法と呼ばれるアプローチで解決できる問題です。残念ながら、私が持っている講義ノートはバイオインフォマティクスに焦点を当てすぎているので、自分でググる必要があります.

于 2008-09-15T17:09:59.587 に答える
2

これは、NP 完全であることが知られている部分和問題のように聞こえます。

頑張ってください。

編集：（1つだけではなく）何らかの額面の任意の数の紙幣/硬貨が許可されている場合、それは別の問題であり、より簡単です. コインの問題を参照してください。（疑わしい）同様の質問に対する別の回答を読んだときに、これに気付きました。

于 2008-09-15T17:15:48.433 に答える
1

この問題は、MattW などの動的計画法の手法で対処できます。言及された。

請求書の数と最大金額が限られている場合は、次の解決策を試すことができます。コード スニペットは C# ですが、他の言語に簡単に移植できると思います。

        // Set of bills
        int[] unit = { 40,20,70};

        // Max amount of money
        int max = 100000;

        bool[] bucket = new bool[max];

        foreach (int t in unit)
            bucket[t] = true;

        for (int i = 0; i < bucket.Length; i++)
            if (bucket[i])
                foreach (int t in unit)
                    if(i + t < bucket.Length)
                        bucket[i + t] = true;

        // Check if the following amount of money
        // can be built additively
        Console.WriteLine("15 : " + bucket[15]);
        Console.WriteLine("50 : " + bucket[50]);
        Console.WriteLine("60 : " + bucket[60]);
        Console.WriteLine("110 : " + bucket[110]);
        Console.WriteLine("120 : " + bucket[120]);
        Console.WriteLine("150 : " + bucket[150]);
        Console.WriteLine("151 : " + bucket[151]);

出力：

15 : False
50 : False
60 : True
110 : True
120 : True
150 : True
151 : False
于 2009-01-01T19:25:34.577 に答える
1

タイラーに同意します-あなたが説明しているのは、 NP-Completeであることが知られているサブセット合計問題の変形です。この場合、限られた値のセットで作業しているため、少し幸運です。ここで動的プログラミング手法を使用して、問題を少し最適化できます。コードの一般的なアイデアについては、次のとおりです。

  • お金を扱っているため、特定の請求書で両替する方法は非常に多く、ほとんどの場合、いくつかの請求書が他の請求書よりも頻繁に使用されます。したがって、結果を保存すると、最も一般的なソリューションのセットを保持し、実際のソリューションを試す前にそれらをチェックすることができます。
  • 使用している言語が再帰をサポートしていない場合を除き、ソリューションでの再帰の使用を完全に無視する理由はありません。再帰的な問題は反復を使用して解決できますが、これは再帰の方が書きやすい可能性が高いケースです。

Kyleやseanyboyなどの他のユーザーの中には、独自の関数を作成するための正しい方向性を示している人もいます。

于 2008-09-15T17:51:50.967 に答える
0

再帰なしと制限付き再帰には違いがあります。レッスンのポイントを逃してしまうので、2 つを混同しないでください。

たとえば、C++ またはその他の低レベル言語で再帰を使用して階乗関数を安全に作成できます。これは、数回の再帰内で最大数のコンテナーでも結果がオーバーフローするためです。したがって、直面する問題は、再帰のためにスタックが吹き飛ばされる前に結果を保存することです。

これは、あなたが見つけた解決策が何であれ、他の人がすでにそれを行っていることがわかっているので、私はあなたの問題を深く理解することさえ気にしませんでした.あなたのアルゴリズムの動作を研究する必要があり、最悪のシナリオの深さを判断することができますあなたのスタックの。

最悪のシナリオがプラットフォームでサポートされている場合は、再帰を完全に回避する必要はありません。

于 2009-01-01T18:43:08.720 に答える
-1

アルゴリズム: 1. 利用可能な通貨単位を降順に並べ替えます。
2. 剰余を計算します = 入力%額面[i] i -> n-1, 0
3. 剰余が 0 の場合、入力を分解できます。それ以外の場合は分解できません。

例:
入力: 50、使用可能:
10,20 [50 % 20] = 10、[10 % 10] = 0、答え: はい 入力: 50、使用可能: 15,20
[50 % 20] = 10、[10 % 15] = 15、答え: いいえ

于 2009-01-01T18:55:16.760 に答える
-1

編集：以下は時々うまくいきます。常に機能しない理由と、他のケースをカバーするためにどのように変更できるかを考えてください。

一番大きい請求書から始めて、一番小さい請求書に向かって作成します。これにより、請求書の数が最も少なくなります。

最初の金額を取り、価格を超えないように何度でも最大の請求書を適用します。

次に大きい請求書に進み、同じ方法で適用します。

あなたがあなたの最小の請求書になるまでこれを続けてください.

次に、合計が目標金額と等しいかどうかを確認します。

于 2008-09-15T17:07:57.780 に答える