Dynamic Programming – Knapsack Problem

01 knapsack problem

Problem Description:

There are N items and a knapsack with capacity V. Each item can only be used once.
The volume of the i-th item is vi, and the value is wi. Solve which items to put into the backpack, so that the total volume of these items does not exceed the backpack capacity, and the total value is the largest.

Solutions:

#include<iostream>
using namespace std;
const int N=1010;
int v[N], w[N];
int f[N][N];
int main(){
    int n,m;
    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=0;j<=m;j++){
            f[i][j]=max(f[i][j],f[i-1][j]);//Do not select the i-th item
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]] + w[i]);
            // select i item
        }
    }
    cout<<f[n][m];
    return 0;
}

This can be optimized with one-dimensional arrays:

To optimize the state f[i][j] to one-dimensional f[j], in fact, only one equivalent transformation is needed.
Why can it be deformed like this? The state f[i][j] we defined can obtain any legal optimal solution of i and j, but the title only requires the final state f[n][m], so we only need one-dimensional space to update state.
(1) Definition of state f[j]: NN items, optimal solution under knapsack capacity j.
(2) Note that the enumerated knapsack capacity j must start from m.
(3) Why is the reverse order required to enumerate the knapsack capacity in a one-dimensional case? In the two-dimensional case, the state f[i][j] is obtained from the state of the last round i – 1, and f[i][j] and f[i – 1][j] are independent. After optimizing to one dimension, if we are still in the positive order, then f[smaller volume] is updated to f[larger volume], it is possible that the state of the i-1th round should be used but the i-th round is used status.
(4) For example, if the i-th round of the one-dimensional state makes a decision on an item with a volume of 33, then f[7] is updated from f[4], where f[4] should be f[i – 1][ 4], but f[4] in enumerating j from small to large becomes f[i][4] in the i-th round of calculation. When enumerating the knapsack capacity j in reverse order, we find that f[7] is also updated by f[4]. However, due to the reverse order, f[4] here has not been calculated in the i-th round, so the actual calculated f[ 4] is still f[i – 1][4].
(5) To put it simply, updating the state f[j] in the positive order of the one-dimensional case needs to use the previously calculated state has been “polluted”, and there will be no such problem in the reverse order.
The state transition equation is: f[j] = max(f[j], f[j – v[i]] + w[i] .

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N];
int main(){
    int n,m;
    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=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]] + w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

Complete knapsack problem

Problem Description:

There are N items and a knapsack of capacity V, and infinite pieces of each item are available.
The i-th item has volume vi and value wi.
Solve which items to put into the backpack so that the total volume of these items does not exceed the capacity of the backpack and the total value is the largest.

The basic idea:

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N], w[N];
int main()
{
    int n,m;
    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 = 0 ; j<=m ;j++ )
    {
        for(int k = 0 ; k*v[i]<=j ; k ++ )
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]] + k*w[i]);
    }

    cout<<f[n][m]<<endl;
}

However, this method will time out, so it needs to be optimized. The optimization idea is as follows:

We enumerate the internal relationship of the update order:
f[i , j ] = max( f[i-1,j] , f[i-1,j-v] + w , f[i-1,j-2v] + 2w , f[i-1,j-3v] + 3w , …)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v] + 2*w , …)
From the above two formulas, the following recurrence relation can be obtained:
f[i][j]=max(f[i,j-v] + w , f[i-1][j])

With the above relationship, in fact, the k cycle can be omitted, and the core code is optimized as follows:

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

This code is very similar to the non-optimized writing method of 01 backpack!!!

f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);//01 backpack

f[i][j] = max(f[i][j],f[i][j-v[i]] + w[i]);//complete knapsack problem

Because it is very similar to the 01 backpack code, we can easily think of further optimization. The core code can be changed to the following

 for(int i = 1 ; i<=n ;i ++ )
    for(int j = v[i] ; j<=m ;j ++ )//Attention, j here is an enumeration from small to large, which is different from the 01 backpack, because the large capacity is determined by the small capacity of the current round renew
    {
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    }

To sum up, the final writing method of the complete knapsack is as follows:

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N], w[N];
int main()
{
    int n,m;
    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 = v[i] ; j<=m ;j ++ )
    {
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    }
    cout<<f[m]<<endl;
}

Multiple knapsack problem

Problem Description:

There are N items and a backpack with capacity V.
There are at most si pieces of the i-th item, each with a volume of vi and a value of wi.
Solve which items to put into the backpack, so that the sum of the volume of the items does not exceed the capacity of the backpack, and the sum of the values is the largest.

Solutions:

The same as the simple version of the complete knapsack problem, that is, when enumerating how many items to choose for each item, add a quantity limit.

#include<iostream>
using namespace std;
const int N=110;
int f[N][N];
int v[N],w[N],s[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i + + )cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i + + ){
        for(int j=0;j<=m;j++){
            for(int k=0;k*v[i]<=j & amp; & amp;k<=s[i];k ++ ){
                f[i][j]=max(f[i-1][j],f[i][j]);
                if(j>=k*v[i]) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]] + k*w[i ]);
            }
        }
    }
    cout<<f[n][m];
}

Multiple knapsack problem 2

Problem Description

There are N items and a backpack with capacity V.
There are at most si pieces of the i-th item, each of which has a volume of vi and a value of wi.
Solve which items to put into the backpack, so that the sum of the volume of the items does not exceed the capacity of the backpack, and the sum of the values is the largest.

data range

0 0 0

Solutions:

Compared with the multiple knapsack problem, the range of data is larger. If the original solution is still used, the time will be exceeded, and a new solution is needed, which is to use binary optimization. The reason why the optimization method of the original knapsack problem cannot be used is because of the limitation of the number of items.

We first confirm three points:

(1) We know that the basic idea of converting it into a 01 backpack is: to judge whether I took the hello or not to take the hello for each item.
(2) We know that any real number can be represented by a binary number, that is, the sum of one or more of 20 2k20 2k.
(3) The question of multiple backpacks here is how many pieces of each item can be taken to obtain the maximum value.

analyze:

If the direct traversal is transformed into the 01 knapsack question, it is better to ask one each time, whether to take it or not. Then according to the data range, the time complexity is O(n3)O(n3), which is 109109, so there is no doubt that it will be TLE.

If it is better to choose 7 out of 10, then in the actual traversal process after the 7th state transition equation, it is actually a good choice to “not take”. Now, use binary thinking to divide it into piles, divide it into k + 1k + 1 piles with 2k2k pieces each, and then take this pile to ask, should I take it or not, after dp selection After that, the result is exactly the same as the result of asking one by one, because dp chooses the optimal result, and according to the second point, any real number can be expressed in binary. If 10 out of 7 are finally selected, it is The optimal ones are divided into four piles of 20=1, 21=2, 22=4, 10?7=320=1, 21=2, 22=4, 10?7=3 during the selection process of the piles, and then Ask four times, that is, take it and go through the dp state transition equation. The result of the walk is 1 in the first pile, which is better to take than not to take, 2 in the second pile, which is better to take than not to take, and four in the third pile , it is better to take than not to take, the fourth pile of 8, it is better not to take, in the end it is still 1 + 2 + 4=71 + 2 + 4=7.
In this way, using binary optimization, the time complexity is reduced from O(n3)O(n3) to O(n2logS)O(n2logS), from 4?1094?109 to 2?1072?107. It is equivalent to the 01 knapsack problem.

#include<iostream>
using namespace std;
const int N=12010,M=2010;
int v[N],w[N];
int f[M];
int main(){
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i + + ){
        int a,b,s;
        int k=1;//binary number
        cin>>a>>b>>s;
        while(k<=s){
            cnt + + ;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0){
            cnt + + ;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    n=cnt;//How many groups are the items divided into, and the following is converted to the 01 backpack problem
    for(int i=1;i<=n;i + + ){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]] + w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

Group knapsack problem

Problem Description:

There are N sets of items and a knapsack of capacity V.
There are several items in each group, and only one item in the same group can be selected at most.
The volume of each item is vij and the value is wij, where i is the group number and j is the number within the group.
Solve which items to put into the backpack so that the total volume of the items does not exceed the capacity of the backpack and the total value is the largest.

Solutions:

The solution to the multiple knapsack problem is the same as that of changing the original quantity limit to a group limit.

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; 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 = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}