9

私は動的プログラミングが初めてで、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.

4

2 に答える 2

9

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

コードでばかげた間違いを犯しています。

まず、入力の最初の整数が重みで、2 番目が値です。最初を値として、2番目を重みとして取っている間。さらに、入力 0 から N までの n+1 値を使用しています。

アルゴリズムでは、アイテムのコピーをいくつでも取得できると考えていますが、これは正しくありません。これは 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;
}

ところで、配列を動的に割り当てるのではなく、単純にベクトルを使用します

vector <int> My_array(n);
于 2012-06-14T21:42:15.043 に答える
3

Pythonのhttps://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-pで十分に文書化されたナップザックの問題のバージョンがあります。

編集: 気にしないで、最初の行の入力が C と N を定義する部分をスキップしました。 <= N)。アイテムとして 0..n-1 を取得するには、ループが < N であることを期待しています。

無意味な 134516145 という結果が出力される問題を修正しました。

于 2012-06-14T16:05:48.060 に答える