The knapsack problem is the classic DP problem.

Backpacks can be divided into the following categories

  1. 01 knapsack
  2. Completely backpack
  3. Multiple backpack
  4. Packet backpack

01 Backpack Problem

The problem

There are n items, each of which has volume V and value W. What is the maximum value that a backpack can carry?

To analyze problems

State: DP [I][j]: put the first I items into the backpack with volume J, and the maximum value in the backpack

State calculation: the main consideration is whether the ith item is currently selected or not. If the current volume > the volume of the current item is optional: v [I] > = j menu: dp [I] [j] = dp [I – 1] [j – v [I]] + w [I]; Don’t choose: dp [I] [j] = dp [I – 1) [j];

Since we’re taking the maximum, we can just take Max before both of them. [n][V]

code

/ / 01 knapsack
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N][N];
int v[N],w[N];
int n,m;
int main(a)
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>v[i]>>w[i];for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(v[i]<=j)// Select the maximum value between select and deselect.
                dp[i][j]=max(dp[i- 1][j],dp[i- 1][j-v[i]]+w[i]);
            else / / not optional
                dp[i][j]=dp[i- 1][j];
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
} 
Copy the code

We can see that this code can be further optimized by using data from the previous row above the current position for each state calculation. So you can optimize scrolling as a one-dimensional array.

//01 knapsack uses one-dimensional array optimization
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N];
int v[N],w[N];
int n,m;
int main(a)
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>v[i]>>w[i];for(int i=1; i<=n; i++) {for(intj=m; j>=1; j--)// Since we need to use the data in column j before the previous row,
        {// So you need to traverse backwards to avoid changing the data you need to use
            if(v[i]<=j)
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
} 
Copy the code

Completely backpack

The problem

There are n items, each of which has volume V and value W. Each item can be used an infinite number of times. What is the maximum value that can be carried in a backpack?

To analyze problems

State representation: DP [I][J]: the first I items into multiple into the backpack volume j, the maximum value in the backpack

State calculation: Since each item can be selected an infinite number of times, it needs to be divided into sets (select 0, 1, 2 for the ith item… K); Then take the maximum line Dp [I] [j] = Max (Dp [j], [I – 1] Dp [I – 1] [j – v [I]] + w [I], Dp [I – 1] [j – kv [I]] + kw [I]); However, this requires a three-layer cycle, and the algorithm is not efficient, so we need to continue to optimize; Dp[i][j-v[i]]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j-kv[i]]+kw[i]);

Dp [I][j]= Max (dp[i-1][J], DP [I][j]]);

code

// Full backpack
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N][N];
int v[N],w[N];
int n,m;
int main(a)
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>v[i]>>w[i];for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) { dp[i][j]=dp[i- 1][j];
            if(v[i]<=j)
                dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
            
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}  
Copy the code

Multiple backpack

The problem

There are n items, each of which has volume V and value W. Each item has s[I]. What is the maximum value that can be carried in a backpack?

Analysis problem:

Multiple backpacks are similar to full backpacks, but limit the number of items per bag

State representation: DP [I][J]: the first I items into multiple into the backpack volume j, the maximum value in the backpack

State calculation: Since each item can be selected an infinite number of times, it needs to be divided into sets (select 0, 1, 2 for the ith item… K); K =min(j/v[I],s[I]); However, due to the limited number of available, it can not be optimized as a full backpack.

Here we can use binary (binary eternal god YYds), for example an item has 11:11 (1011) =7 (0111) +4 (0100); Divide 11 into numbers smaller than 11, the largest number at the end of the binary with all 1s + the rest of the number, and then you can divide 11 items into 4 piles: 1 (0001), 2 (0010), 4 (0100), 4 (0100), these 4 piles of items can be selected and not selected and then can be combined into 0-11 items, after each push can only be used once, the 4 push items set, has become 01 backpack problem.

Code:

// Multiple backpacks
#include<bits/stdc++.h>
using namespace std;
const int N = 2005*11;
int dp[N];
int v[N],w[N];
int n,m;
int main(a)
{
    cin>>n>>m;
    int cnt=0;
    for(int i=1; i<=n; i++) {int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s)// Divide s into items such as 11 (1011) into 0001,0010,0100;
        {
            v[++cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k<<=1;
        }
        if(s>=0)// 11 (1011) -7 (0111) =4{ v[++cnt]=a*s; w[cnt]=b*s; }; }for(int i=1; i<=cnt; i++)// Make 01 knapsack for item set
    {
        for(intj=m; j>=1; j--) {if(v[i]<=j) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}  
Copy the code

 

Grouping knapsack problem:

The problem

There are n groups of items, each of which has volume V and value W. There is also a backpack with a volume of V, each group can only choose one item at most, ask what is the maximum value that the backpack can carry.

To analyze problems

The state represents: DP [I][j]: the maximum value of the items in the former I group is put into the backpack with volume J

Status calculation: only one item per group can be used. Need to divide collection current group (select 0, select 1, select 2, select 3… K); Dp [I] [j] = Max (Dp [j], [I – 1] Dp [I – 1] [j – v [I] [1]] [1], [I] + w… , dp [I – 1] [j – v [I] [k]] + w [I] [k])

Code:

// Pack backpacks
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int dp[N];
int main(a)
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 1; k <= s[i]; k ++ )
                if (v[i][k] <= j)
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
    cout << dp[m] << endl;
    return 0;
} 
Copy the code