整数ナップザックを解決する

Question

私はダイナミックなプログラミングには新しく、ここでは整数ナップザック問題をSPOJ (http://www.spoj.pl/problems/KNAPSACK/で試しました。しかし、特定のテストケースでは、私の解決策は正しい出力を出すことができません。私の次の実装が正しいかどうかを提案できれば、あなたに感謝します。変数backはバックトラッキングのためのものであり、その方法についてはわかりません。私はバックトラックの実装にもあなたの助けを借りて願っています。ありがとう。ここで

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

using namespace std; 

int knapsack(int value[], int weight[], int n, int C, 
     vector <int>&back) 
{ 
    int *M = new int[C + 1]; 
    int k; 
    int i, j, tmp, pos; 
    for (i = 1; i <= C; i++) { 
     M[i] = M[i - 1]; 
     pos = i - 1; 
     for (j = 0; j < n; j++) { 
      k = i - weight[j]; 
      if (k >= 0) 
       tmp = M[k] + value[j]; 
      if (tmp > M[i]) { 
       M[i] = tmp; 
      } 
     } 
     back.push_back(pos); 
    } 
    int ans = M[C]; 
    delete[]M; 
    return ans; 
} 


int main() 
{ 
    int C, N; 
    cin >> C >> N; 
    int* value = new int[N+1]; 
    int* weight = new int[N+1]; 
    for (int i = 0; i <= N; i++) { 
     cin>>value[i]>>weight[i]; 
    } 
    vector <int>back(N, 0); 
    cout<<knapsack(value,weight,N,C,back)<<endl; 
    return 0; 
} 

正しい入力/出力テストケースは以下のとおりです。

Input: 
4 5 
1 8 
2 4 
3 0 
2 5 
2 3 


Output: 
13 

はしかし、私は取得しています出力は17です。

Answer 1

これは0-1のナップザックとして知られているナップザックの問題のバージョンです。

あなたのコードでいくつかのばかげた誤りがあります。

入力の最初の整数は重みであり、2番目の値は値です。あなたが価値として第一をとっている間、そして重さとして第二に。さらに、n + 1の値を入力0からNに取り込みます。

あなたのアルゴリズムでは、アイテムのコピーをいくつでも取ることができると考えていますが、これは0-1のナップザックです。このhttp://en.wikipedia.org/wiki/Knapsack_problemをお読みください。

私はこのアルゴリズムを考え出し、提出して受け入れました。これはうまくいくはずです。

int M[2000][2000]; 
int knapsack(int value[], int weight[], int C, int n) 
{  
    for(int i = 1; i <= C; i++){ 
    for(int j = 0; j <n; j++){ 
     if(j > 0){ 
     M[j][i] = M[j-1][i]; 
     if (weight[j] <= i) 
      M[j][i] = max(M[j][i], M[j-1][i-weight[j]]+value[j]); 
     } 
     else{ 
     M[j][i] = 0; 
     if(weight[j] <= i) 
      M[j][i] = max(M[j][i], value[j]); 
     } 
    } 
    // cout << M[i][n-1] << endl; 
    }   
    return M[n-1][C]; 
} 

int main() 
{ 
    int C, N; 
    cin >> C >> N; 
    // cout << C << endl; 
    int* value = new int[N+1]; 
    int* weight = new int[N+1]; 
    for (int i = 0; i < N; i++) { 
     cin>>weight[i]>>value[i]; 
    } 
    // vector <int>back(N, 0); 
    cout<<knapsack(value,weight,C,N)<<endl; 
    return 0; 
} 

はBTW動的単に

vector <int> My_array(n); 

Answer 2

Pythonでhttps://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-pによく書かれているナップザック問題のバージョンがあります。

EDIT：Nevermindでは、最初の行入力がCとNを定義している部分をスキップしました。つまり、あなたの入力例は、あなたが提供したコードではロードされていないようです< = Nのために期待される）。私はそのループが< Nであり、アイテムとして0..n-1を得ると期待しています。

134516145という結果が得られたことを修正しました。これは無意味です。