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

问题描述

我一个新的动态编程，并曾试图整数背包问题在这里SPOJ 上（http：// www.spoj.pl/problems/KNAPSACK/ ）。然而，对于给定的测试案例我的溶液是不给正确的输出。我很感谢你，如果你可以建议，如果下面的执行情况我是正确的。请注意，变量返回是出尔反尔，对此我不知道该怎么办。我希望能有你在执行回溯过帮助。谢谢你。

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

不过，我得到的输出为 17 。

推荐答案

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

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

您正在在code一些愚蠢的错误。

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背包。阅读<一个href="http://en.wikipedia.org/wiki/Knapsack_problem">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屋！