0-1整数ナップザックが間違った答えを返す（動的プログラミング）

Question

タイトルはかなりわかりやすく、私は数日間それを手にしています。私が間違っているのはどういう愚かなことですか？問題は、同じ重さで、値の入力ベクトルがないので、std :: maxの部分に値を追加していない可能性がありますが、それをやってみたが、正しい答えも得られなかった。 Wはナップザックの容量、wはアイテムの重みからなるベクトルです。

#include <iostream> 
#include <vector> 

using std::vector; 
using std::max; 

int optimal_weight(int W, const vector<int> &w) { 
    size_t size = w.size(); 
    int knapsack[size+1][W+1]; 

    for (size_t a = 0; a <= size; a++) { 
     knapsack[a][0] = 0; 
    } 

    for (int b = 0; b <= W; b++) { 
     knapsack[0][b] = 0; 
    } 

    for (size_t i = 1; i <= size; i++) { 
      for (int j = 0; j <= W; j++) { 
        knapsack[i][j] = knapsack[i-1][j]; 

        if (w[i-1] <= j) { 
          knapsack[i][j] = std::max(knapsack[i-1][j-w[i-1]], knapsack[i-1][j]); 
        } 

       } 
     } 
     return knapsack[size][W]; 
    } 

Answer 1

コードの行：int knapsack[size][W+1]

に変更しなければならない：int knapsack[size+1][W+1]

これは、アレイは0から索引付け、および0 to size-1ための上記で定義された場合には、あなたがアクセスしているされているので要素はindex = sizeです。 また、std::maxを計算中に対応する重みを追加します。