knapsack problem

Given a group of items, each item has its own weight value. Within the limited weight, how can we choose to maximize the total value.

Three kinds of backpacks

1. 01 backpack: each item can only be selected once
2. Complete backpack: there is no limit to the number of choices for each item
3. Multiple backpacks: each item can only be selected a limited number of times

1, 01 Backpack

Core idea:
In each choice, you only need to consider whether to take it or not, and compare the benefits of the two cases.

V [i] is the weight of the ith article and w [i] is the value of the ith article;

Take the i-th item. When the backpack capacity is j:
dp [ i ] [ j ] = dp [ i - 1 ] [ j - v [ i ] ] + w [ i ] ;

If you don't take the i-th item and the backpack capacity is j:
dp [ i ] [ j ] = dp [ i - 1] [ j ];

State transition equation
dp [ i ] [ j ] = max ( dp [ i - 1] [ j ] , dp [ i - 1 ] [ j - v [ i ] ] + w [ i ] );

Core code

for(int i = 1 ; i <= n ; i++){
  for(int j = 1 ; j <= m ; j++){
      dp[i][j]=dp[i-1][j];  //Don't take the i-th item
      if(v[i]<=j){        //The i-th item can be packed on the back
          dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
      }
  }

One dimensional optimization (optimization space complexity)

When we change two dimensions into one dimension, the array is only related to j. In the i-th cycle, the non updated DP [j] array retains the value of the previous cycle, that is, DP [I - 1] [j], and the updated array is the value of DP [i] [j]. In the state transition equation, we just want the value of DP [I - 1] [j], so we need to update the array in reverse.

for(int i=1;i<=n;i++){
    for(int j=m;j>=v[i];j--){
        dp[j]=max(dp[j],w[i]+dp[j-v[i]]);
    }
}

2, Complete Backpack

Naive algorithm

Add a layer of circulation on the basis of 01 backpack.

for(int i=1;i<=n;i++){
    for(int j=1;j>=w[i];j--){
        for(int k=0;k<=j/w[i];k++){
            dp[j]=max(dp[j],dp[j-v[i]*k]+w[i]*k);
        }
    }
}

However, this is a triple cycle, and the time is too complex.

How can we optimize this algorithm? The final result is very simple, 01 knapsack reverse traversal, complete knapsack forward traversal. The next step is the derivation process. If you find it too difficult, you can skip the result directly.

Logic behind the algorithm

In the complete backpack, we can take 0 items, 1 items, K items and so on until the backpack can't fit. We analyze K items. When we take the ith item of K items, we require the maximum value of DP [I - 1] [J - k * V [i]]
For convenience, v [i] and w [i] are expressed as V, W;

dp [ i ] [ j ] = max ( dp [ i - 1 ] [ j ] , dp [ i - 1] [ j - v ] + w ,
dp [ i - 1 ] [ j - 2 * v ]+2 * w , ... ...);

Namely:
dp [ i ] [ j - v ] =max( dp [ i - 1 ] [ j - v ] , dp [ i - 1 ] [ j - 2 * v ] + w ,
dp [ i - 1 ] [ j - 3 * v ] + 2 * w , ... ...);

A magical thing happened. The maximum value of the following formula plus w is the removal of the above formula
Other maxima of DP [I - 1] [J], so we can get the state transition equation

for(int i = 1 ; i <= n ; i++){
  for(int j = 1 ; j <= m ; j++){
      dp[i][j]=dp[i-1][j];  //Don't take the i-th item
      if(v[i]<=j){        //The i-th item can be packed on the back
          dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
      }
  }

Just a little different from 01 backpack. Let's take a look at optimization.

One dimensional optimization (optimization space complexity)

When we change two dimensions into one dimension, the array is only related to j. In the i-th cycle, the non updated DP [j] array retains the value of the previous cycle, that is, DP [I - 1] [j], and the updated array is the value of DP [i] [j]. This time we need the value of DP [i] [j] in the state transition equation, so we need to update the array in the forward direction this time.

for(int i=1;i<=n;i++){
    for(int j=v[i];j<=m;j++){
        dp[j]=max(dp[j],w[i]+dp[j-v[i]]);
    }
}

It can be compared with 01 backpack.

3, Multiple Backpack

Naive algorithm

S [i] indicates how many items can be taken for the ith item.

for(int i=1;i<=n;i++){
    for(int j=1;j>=w[i];j--){
        for(int k=0;k<=s[i]&&v[i]*k<=j;k++){
            dp[j]=max(dp[j],dp[j-v[i]*k]+w[i]*k);
        }
    }
}

Unpacking optimization

The number of each item can be loaded into the backpack, which can be transformed into 01 backpack problem
Packing code:

int k=n+1;
for(int i=0;i<n;i++){
     while(s[i]>1){
         v[k]=v[i];
         w[k]=w[i];
         k++;
         s[i]--;
    }
}

Then use the 01 knapsack solution above to solve the problem.

Binary optimization method

Divide the items into n-th power of 2 and put them into the backpack. In this way, any number can be formed.
For example: there are 7 items at present, which are disassembled into 1, 2 and 4 and put into the backpack. That is, take 1 to 7 items, which can be combined by these three with or without.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,dp[500005];
struct Good{
   int v,w;
};
int main(){
   cin>>n>>m;
   vector<Good>goods;
   //Unpacking
   for(int i=1;i<=n;i++){
      int v,w,s;
      cin>>v>>w>>s;
      for(int k=1;k<=s;k*=2){
          s-=k;
          goods.push_back({w*k,c*k});
       }
   if(s>0){//Put the remaining pieces into the backpack
       goods.push_back({s*w,s*c}); 
   }  
 }
 /*for(auto good: goods){
  for(int j=m;j>=good.v;j++){
   dp[j]=max(dp[j],dp[j-good.v]+good.w);
  }
 }*/
 //Next, treat it directly as 01 backpack
 for(int i=0;i<=goods.size();i++){//Notice here that the subscript of the vector array
 //It starts from 0. The type of items in the backpack is no longer n, but the size of the vector array 
      for(int j=m;j>=goods[i].w;j--){
           dp[j]=max(dp[j],dp[j-goods[i].w]+goods[i].c);
      }
 } 
 cout<<dp[m]<<endl;
 return 0;
}