Convenient for self review ==

1.01 Backpack

Problem Description: there are n valuable items and a backpack with a volume of v. there is one for each item. Calculate the maximum value of the items that the backpack can hold.

Analysis process:

1. Describe the state: we use f [i] [j] to indicate that only the first I items are selected, and the total volume is less than or equal to the maximum volume of j. this is what we call the state representation. The attribute is max, that is, the maximum value.

2. Calculation of equation of state: select or deselect to update f [i] [j]. For the ith item, we can select or deselect. If we do not select the ith item, then f [i] [j] = f [i - 1] [j], which is equal to the value of our previous equation of state. If we select the ith item, we can also update it with the equation of the previous layer, F [i] [j] = f [i - 1] [j - v [i] + w [i] (this step is very important) explain this equation. When we select the i-th item, it is actually equivalent to removing the item with volume v [i] from the i-1st layer and adding the value of the i-th item, Since layer I-1 has been considered as the maximum value calculated that the total volume selected from I-1 does not exceed j, layer I of the ith item is to calculate the volume of object I removed from layer I-1 plus its value. It is worth noting that in order to prevent our array from crossing the boundary, We need to ensure that the enumerated j is greater than or equal to the volume v [i] of the ith article.

3. Update of the equation of state: from 2, we can know that for the i-th item, we have two equations to calculate. Because it is to find the maximum value, we get the general equation of state transition, f [i] [J] = max (f [I - 1] [J], f [I - 1] [J - v [i] + w [i]).

4. Optimization of state transition equation: if we write too much, we will know that for the optimization of knapsack problem, we usually optimize the dimension of the equation. When we remove the first dimension of the equation, f [J] = max (f [J], f [J - v [i] + w [i]), for f [J], for not selecting the ith item, f [i] [J] = f [i - 1] [J], So f [J] is actually equivalent to f [i] [J]. For selecting the ith item, f [J - v [i] + w [i] is also iterated from the upper layer. If J is enumerated from large to small, f [J - v [i] < J will be updated when we update f [J], so that f [J] we use is f [J] of layer I, not layer i - 1, For example, for the ith article with Volume 1, when j = 3, f [3] = max (f [3], f [3 - 1] + w), and when J continues to traverse equal to 4, f [4] = max (f [4], f [4 - 1] + w), we can see that the f [3] used when j = 4 has actually been updated, Because it is still the i-th item at this time, it will cause that the f [J - v [i]] we use is not in the upper layer cycle, so this problem will not occur when traversing j from large to small. Similarly, using the above example, we update f [4] first, and then update f [3] without using the i-layer state.

Code implementation:

Non optimized version

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

Optimized version:

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

2. Complete Backpack

Problem Description: there are n valuable items and a backpack with a volume of v. there are countless items for each item. Calculate the maximum value of the items that the backpack can hold.

Analysis process:

1. Describe the state: like the 01 knapsack problem, we also use f [i] [J] to represent the state of the problem, and then select the optimal solution with the total volume not exceeding j from the first I items. Property is still the maximum value.

2. Calculation of equation of state: for the i-th item, we can select 0 ~ times to maximize the value when the volume does not exceed j. when we update the i-th item, there are also cases of not selecting and selecting k times. If it is not selected, the equation of state is calculated as f [I] [j] = f [I - 1] [j]; There is the following formula for selecting the i-th item

max (  f [ i - 1 ] [ j -  v ] +  w, f [ i - 1] [ j - 2 * v ] + 2 * w ...... )； 

So f [i] [j] = max (f [i] [j], f [I - 1] [j - v] + W, f [i] [j - 2 * V] + 2 * w...);

Can be found

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

3. Update of equation of state: compared with the blue part, we can find that the equation of state that can be updated is:

f [ i ] [ j ] = f [ i - 1 ] [ j ];

f [ i ] [ j ] = max ( f [ i ] [ j ], f [ i ] [ j - v ] + w );// Without crossing the line

4. Optimization of state equation: the optimization equation is also used to remove a dimension to realize optimization

When one dimension is removed, f [j] = max (f [j], f [j - v] + W); We can easily find that the correctness of the algorithm can still be ensured when j passes from small to large after removing this one dimension, because f [j - v] uses the data of layer I, i.e. f [i] [j - v]. The principle is the same as that of 01 knapsack, which will not be repeated here.

Code implementation:

1. Non optimized version

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

    return 0;
}

2. Optimized version

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

3. Multiple knapsack problem 1

Problem Description: basically consistent with the complete knapsack problem, the number of items has changed from infinite to limited.

Process analysis:

Not much analysis. It is basically consistent with the complete knapsack. The differences are analyzed below

For the state description of multiple backpacks, we can select 0 ~ k items for each item. When analyzing and selecting the ith item, we can have:

Uncheck the ith: F [i] [J] = f [I - 1] [J]

Select the ith item of K times: F [i] [J] = max (f [i] [J], f [i] [J - k * V] + k * W);

It can be found that the above two conditions can be realized by a loop traversing k.

Optimization of multiple knapsack: multiple knapsack can't be dimensionally optimized like complete knapsack. It can only be written in ordinary version. The reason is that the number of items in complete knapsack is unlimited, while the items in multiple knapsack are limited. The blue part of complete knapsack mentioned above can be priced equally because its number can be obtained infinitely, but the multiplicity is different, If you don't understand here, you can write it yourself and understand it more deeply.

Code implementation:
 

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

In fact, when the data given in the title is small, you can do it according to the solution of 01 knapsack:

#include<iostream>
using namespace std;
const int N = 11000;
int f[N], w[N], v[N];
int main()
{
    int n, m, t = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        while(c --)
        {
            w[++t] = b;
            v[t] = a;
        }
    }
    for(int i = 1; i <= t; i ++)
        for(int j = m; j >= v[i]; j --)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[m] << endl;
    return 0;
}

4. Multiple knapsack problem 2

Problem Description: it is the same as the above problem, but the range of data is large. Following the above method will lead to timeout.

Here, the optimization method is directly given: binary optimization to process data and 01 knapsack to solve problems.

What is binary optimization:
For example, there are k items in the i-th item, and this k is very large. If you directly process the data according to the idea of solving the problem of 01 knapsack, it will burst the stack, so there is the next binary optimization;

For K, we can regard it as a binary form and process the data with the idea of multiplication, for example, k = 1101, i.e. k = 14. If a data storage is carried out for each article, it will take 14 units to store, then we divide it into multiple numbers 1, 2 and 4 ﹐ the combination of these three numbers can represent any integer between 1 and 7, Add a bit 14 - 1 - 2 - 4 = 7 to form the four numbers 1, 2, 4 and 7. The combination can represent any integer between 1 and 14. When we iterate the equation of state, our best choice for I is still between 0 and 14, Therefore, when we store 14 I items with binary optimization into the four numbers of 1, 2, 4 and 7, and then iterate, we can achieve the same effect as each storage iteration, and change the complexity from O(n) to O(log n)

Code implementation: / / binary + 01 knapsack optimization

#include<iostream>
using namespace std;
const int N = 12010;
int v[N], w[N], f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int k = 1;
        while(k <= c)
        {
            w[++cnt] = k * b;
            v[cnt] = k * a;
            c -= k;
            k *= 2;
        }
        
        if(c > 0)
        {
            w[++cnt] = c * b;
            v[cnt] = c * a;
        }
    }
    
    for(int i = 1; i <= cnt; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

5. Group knapsack problem

Problem Description: there are n groups of items, each group has s items, and the value of items in each group is different. There is also a backpack with the size of v. each group can only hold one item. Ask what the maximum value can be.

Process analysis:

In fact, this thing is similar to 01 knapsack. For group i items, we can choose not to use it or choose to use the k-th item. Then we can write it directly according to the optimization solution of 01 knapsack and add a double cycle.

Code implementation:
 

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

End!