0

私が問題を抱えている質問は次のとおりです。
私が与えられた重量の貯金箱を持っていて、与えられたコインのセットを使ってそこにお金を節約しているとしましょう。最後に、私は貯金箱の総重量と私が使用していたコインの重量と価値を知っています。

貯金箱に入れることを保証できる最低金額、つまり最悪のシナリオを知りたいです。たとえば、次の場合：

  • 総重量=100
  • 使用したコインの重さ={1、50}
  • コインの価値={1、30}

その場合、私が保証できる銀行の最小値は60です。

質問はナップザックの変種ですが、正しい再発を見つけることができません。

前もって感謝します！

4

3 に答える 3

1

私がこれに取り組む方法は、セット内の各コインを評価して、その「価値密度」（より良い用語が必要な場合）（値を重量で割ったもの）を決定することです。あなたの例では、最初のコインの値密度は1で、2番目のコインの値密度は30/50=0.6です。

次に、総重量をゼロから始めて、指定された重量を超えずに、可能な限り低い「値密度」のコインを適用します。次に、指定された重量に達するまで、次に低い「値密度」コインなどを適用します。

これは大まかに欲張りアルゴリズムです。

于 2012-05-22T10:55:57.567 に答える
0

一般的にナップサック問題AFAIKには指数関数的な解決策しかありません。つまり、すべての種類のコインの特定の量があるとします。最も一般的なケースでは、可能なすべての組み合わせを試す必要があります（もちろん全体の重量を超えないようにしてください）。

再帰的アルゴリズムは次のようになります。

const int N = /* type count*/;

const int g_Weight[N] = { ... };
const int g_Value[N] = { ... };

int CalcMinValueFrom(int weight, int i)
{
    int valBest = 0, valMy = 0;

    if (weight <= 0)
        return 0; // weight already reached

    if (i >= N)
        return -1; // out of coins

    while (true)
    {
        int valNext = CalcMinValueFrom(weight, i+1);
        if (valNext >= 0)
        {
            valNext += valMy;
            if (!valBest || (valBest > valNext))
                valBest = valNext;
        }

        valMy += g_Value[i];
        weight -= g_Weight[i];

        if (valBest && (valBest <= valMy))
            return valBest;
    }
}

// Returns the minimum value for the given weight    
int CalcMinValue(int weight)
{
    return CalcMinValueFrom(weight, 0);
}

ただし、特定のケースでは、より良い解決策があります。重量がどのコインの重量よりもはるかに大きい場合は、結果を簡単に概算できます。すべてのコインについて、その「効率」をその価値と重量の比率として定義します。値を最小化するには、「効率」が最も低いコインのみを選択する必要があります。このソリューションは、丸めなどの「エッジ効果」まで正確です（つまり、整数個のコインしか取得できません）。

于 2012-05-22T10:43:38.240 に答える
0

どうやらあなたは問題を知っていますが、あなたは解を計算する方法を手に入れたいと思っています^^。

正確な方法については、分枝限定アルゴリズムを確認できます。これは、ナップサック問題の正確な解決策を見つけるための比較的簡単なOR方法であり、多くのコースを見つける必要があります。

Vickyは、分枝限定アルゴリズムの下限を計算するための優れたソリューションを提出しました。

于 2012-05-22T12:30:45.457 に答える