I was recently solving a knapsack problem. In this version of knapsack, instead of weight, value is taken into the state.
The problem is the same as general Knapsack: There are n items, Item i has a weight of wi and a value of vi. The capacity of the knapsack is W. Find the maximum possible sum of the values of items that can be filled in the knapsack.
Constraints: 1<= n <=100 1<= W <=10^9 1<= wi <=W 1<= vi <=1000
Input: n W
w1 v1 w2 v2 w3 v3 ..... wn vn
Due to large value of weight, We have to take value in the state and the result will be the minimum weight. Although I have explained the problem but in case you need more details this is the problem link.
The below code is my attempt to solve the problem. I have used 1-based indexing. I'm not able to find out the error. I have tried debugging the code but that didn't help. I'm stuck on this from 2 days. Please help.
  #include <iostream>
  #include <limits.h>
  using namespace std;
  int main()
  {
    int n,W;
    cin>>n>>W;    // no. of elements and maxm. Weight
    int v[n+1],w[n+1];   // array for value and weight 
    int dp[n+1][100001];  // dp array with size n+1 and 10^5+1 (for v max value 1000, and for n 100)
    // Initializing arrays
    v[0]=INT_MAX; w[0]=INT_MAX;
    for (int i = 0; i < n+1; ++i)
    {
      for (int j = 0; j < 100001; ++j)
      {
        dp[i][j]=INT_MAX;      
      }
    }
    for (int i = 1; i < n+1; ++i){
      cin>>w[i]>>v[i];
    }
    
    dp[1][0]=0; // for 0 value, no value for weight
    dp[1][v[1]]=w[1]; 
    
    for (int i = 2; i < n+1; ++i) 
    {
      dp[i][0]=0;
      
      for (int j = 1; j < 100001; ++j)
      {
        dp[i][j]=dp[i-1][j]; // excluding the element
        if(j-v[i]>=1){ 
          dp[i][j]=min(dp[i][j],w[i]+dp[i-1][j-v[i]]); // min of including and excluding element
        }
      }
    }
    // to find the max value for which weight is <=W
    for(int i=100000; i>=1; i--){
      if(dp[n][i]<=W){
        cout<<i; break;
      }
    }
    return 0;
  }
Aucun commentaire:
Enregistrer un commentaire