解决整数背包 [英] Solving the Integer Knapsack

问题描述

我是一个新的动态编程，并尝试整体背包问题在这里SPOJ （http://www.spoj.pl / problems / KNAPSACK / ）。然而，对于给定的测试用例，我的解决方案没有给出正确的输出。我会感谢你，如果你可以建议如果我的以下实现是正确的。请注意，变量 back 是用于回溯，我不知道如何做。我希望能帮助你实现回溯。感谢。

I a new to dynamic programing and have tried the integer knapsack problem here at SPOJ (http://www.spoj.pl/problems/KNAPSACK/) . However, for the given test cases my solution is not giving the correct output. I'd be thankful to you if you could suggest if the following implementation by me is correct. Please note that the variable back is for backtracking, about which I'm not sure how to do. I hope to have your help in implementing the backtracking too. Thanks.

#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;
}

这里是正确的输入/输出测试用例：

Here are the correct input/output test cases:

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


Output:
13

$ b b

但是，我得到的输出是 17 。

推荐答案

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

This is a version of the Knapsack problem known as the 0-1 knapsack.

你在代码中犯了一些愚蠢的错误。

You are making some silly mistakes in your code.

开始输入中的第一个整数是权重，第二个是值。当你以第一个值作为价值，第二个作为体重。此外，你将n + 1个值作为0到N的输入。

To begin with the first integer in input is the weight and the second is the value. While you are taking first as value and second as weight. Moreover you are taking n+1 values as input 0 to N inclusive.

现在在你的算法中，你考虑可以取任何数量的项目副本，这不是真的这是一个0-1背包。请阅读此 http://en.wikipedia.org/wiki/Knapsack_problem 。

Now in your algorithm, you are considering that you can take any number of copies of the items, this is not true this is a 0-1 knapsack. Read this http://en.wikipedia.org/wiki/Knapsack_problem .

我想出了这个算法，我提交并被接受。所以这应该工作正常。

I came up with this algorithm and I submitted and got accepted. So this should work fine.

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不要使用向量动态分配数组

BTW don't dynamically allocate arrays simply use vectors

vector <int> My_array(n);

这篇关于解决整数背包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！