c++ - ナップサック DP 取られた価値の総数を見つける方法は?

Question

みたいな

最大重量 3

Value Weight 

1955    1
2000    5
101     1

1番目と3番目を取ります。しかし、合計値を見つけることができません。1955+101。

私はナップサック0-1を使っています。とにかく、配列から 1955+101 を見つける方法はありますか

Answer 1

2 つの配列値とwt 、およびナップザックの最大容量である別の変数initial_capacityがあるとします。次に、最初に達成できるmaxValueを計算するdp関数を最初に呼び出す必要があります。再構築関数は、maxValue を達成するためにどのアイテムを取得する必要があるかを示します。

int dp(int position, int weight)
{
    if(position == no_of_items) return 0;
    if(mem[position][weight] != -1) return mem[position][weight];

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    return mem[position][weight] = max(r1, r2);
}

void reconstruct(int position, int weight)
{
    if(position == no_of_items) return;

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    if(r2 > r1)
    {
        cout << "Take item at position : " << position << endl;
        reconstruct(position + 1, weight - wt[position]);
    }
    else
    {
        reconstruct(position + 1, weight);
    }
}

int main()
{
    //read input here
    memset(mem, -1);
    int maxValue = dp(0, initial_capacity);
    cout << "Max value : " << maxValue << endl;
    reconstruct(0, initial_capacity);
}

再構築は貪欲な方法で機能することに注意してください。どちらの決定 (項目を取得するか、項目をスキップするか) が maxValue につながる場合、その決定が行われます。あなたの決定が特定のアイテムを取ることを伴う場合、そのアイテムのインデックスを出力します。

お役に立てれば ：）