0

ナップザックに最適な重みのセットを入れることで得られる最大値を与えるコードがあります。

int arr[5] = {0, 0, 0, 0, 0};
int Weight[5] = {2, 5, 8, 7, 9};
int Value[5]  = {4, 5, 7, 9, 8};
const int n = 5;
const int maxCapacity = 20;

int maximum(int a, int b)
{
    return a > b ? a : b;
}

int knapsack(int capacity, int i)
{
    if (i > n-1) return 0;

    if (capacity < Weight[i])
    {
        return knapsack(capacity, i+1);
    }
    else
    {
        return maximum (knapsack(capacity, i+1),
                        knapsack(capacity - Weight[i], i+1) + Value[i]);
    }
}

int main (void)
{
    cout<<knapsack(maxCapacity,0)<<endl;
    return 0;
}

最適な解を見つけるために使用されるすべての重みを印刷して、この解を拡張する必要があります。このために、0 に初期化された配列 arr を使用する予定です。重みが使用されるたびに、arr の対応する位置を 1 でマークします。それ以外の場合は 0 のままです。

最初に頭に浮かんだのは、以下に示すように maximum() 関数を変更することです

int maximum(int a, int b, int i)
{
    if (a > b)
    {
        if (arr[i] == 1) arr[i] = 0;
        return a;
    }
    else
    {
        if (arr[i] == 0) arr[i] = 1;
        return b;
    }
}

ただし、このソリューションでさえ、重みと値の組み合わせによっては失敗します。前進する方法について何か提案はありますか？

4

1 に答える 1

0

問題は、このコマンドで 2 つのオプションのどちらが選択されているかわからないことです。

return maximum (knapsack(capacity, i+1),
                knapsack(capacity - Weight[i], i+1) + Value[i]);

2 つの変数を使用して値を格納できると思います。重みが選択されている場合 (その変数の値が大きい場合)、それを配列に追加できます。問題が解決することを願っています。

于 2012-10-29T07:11:42.543 に答える