1

私は動的計画法が初めてで、最初の DP 問題を試しました。問題文は

サイズ C のナップザックと、値 v[] を持つサイズ s[] の n 個のアイテムが与えられた場合、ナップザックに入れることができるアイテムの容量を最大化します。項目は何度でも繰り返すことができます。(重複するアイテムは許可されます)。

再帰関係を定式化してDPテーブルを作成し、最終的にナップザックに入れることができる最大値を取得することはできましたが、必要な合計を取得するためにどの値を選択する必要があるかを取得する方法を考案することはできません. .

これが私の解決策です：

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int s[] = { 1, 3, 4, 5, 2, 7, 8 , 10};
    int v[] = { 34, 45, 23, 78, 33, 5, 7 , 1};
    int n = ( (sizeof(s)) / (sizeof(s[0])) );
    vector<int> backtrack;
    int C = 15;
    int pos;
    int m[20];
    m[0] = 0;
    int mx = 0;
    for ( int j = 1; j <= C; j++) {
        mx = 0;
        m[j] = m[j-1];
        pos = j-1;  
        for ( int i = 0; i < n; i++) {
            mx = m[i-s[i]] + v[i];
            if ( mx > m[i] ) {
                m[i] = mx;
                pos = i - s[j];
            }
        }   
        backtrack.push_back(pos);
    }
    cout << m[C] << endl<<endl;
    for ( int i = 0; i < backtrack.size(); i++) {
        cout << s[backtrack[i]]  <<endl;
    }   
    return 0;
}

私の解決策では、選択された最大値アイテムの位置をベクトルに保存し、最終的にそれらを印刷しようとしました。ただし、これでは正しい解決策が得られないようです。

プログラムを実行すると、以下が生成されます。

79

2
3
0
5
2
7
8
10
34
45
23
78
33
5
7

出力に示されているように、サイズ 0 の項目がないため、出力の数値が選択された項目のサイズではないことは出力から明らかです。

私のロジックまたは実装でエラーを見つけるのを手伝ってくれることを願っています。ありがとう。

4

1 に答える 1

0

あなたは貪欲なアプローチに従っています。それはかなり賢いですが、ヒューリスティックです。宿題かもしれないので、正しいコードは示しませんが、再帰関数knapsackは次のようになります。

knapsack(C): maximum profit achivable using a knapsack of Capacity C
knapsack(C) = max { knapsack(C-w[i]) + v[i] } for all w[i] <= C
knapsack(0) = 0

コード内:

dp(0) = 0;
for i = 1 to C
  dp(i) = -INF;
  for k = i-1 downto 0
     if w[k] < i then
        dp(i) = max{dp(i-w[k]) + v[k], dp(i)};
print dp(Capacity);
于 2012-06-29T13:49:44.553 に答える