解决整数背包问题

Question

解决整数背包问题

c++algorithmdynamic-programmingknapsack-problem

8

我是一名新手，尝试在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。

- hytriutucx

1

然而，对于给定的测试用例，我的解决方案没有给出正确的输出。您是指哪个输入？您认为什么样的输出是正确的？而实际上您得到了什么样的输出？ - abelenky

2个回答

3

这里有一个关于背包问题的版本在https://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p上，使用Python编写并有详细文档。

编辑：不好意思，我跳过了输入的第一行定义C和N的部分。但是，您提供的示例输入似乎无法与代码一起加载（由于 <= N，它正在寻找一个多余的配对）。我认为循环应该是 < N，以获取0..n-1作为项目。

修复后，我获得了一个无意义的结果134516145。

- Godeke

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sukunrt · Accepted Answer

这是Knapsack问题的一个版本，被称为0-1背包问题。

您的代码中存在一些愚蠢的错误。

首先，输入中的第一个整数是重量，第二个整数是价值。而您将第一个整数视为价值，第二个整数视为重量。此外，您将n + 1个值作为输入，从0到N（包括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;
}

顺便提一下，不要动态分配数组，改用向量。

vector <int> My_array(n);