01 knapsack problem

https://www.acwing.com/problem/content/2/

Video Explanation: https://www.acwing.com/video/214/

problem analysis

There are n items in this problem, and each item has two attributes. It is required that the method to obtain the maximum value under the restriction of volume V and the maximum value to be obtained

Idea:

Before understanding dp, the first idea is dfs or bfs, but there are two disadvantages: one is that the time complexity is too high, the other is too stupid, and the time complexity is O (N!), The data range of 1000 is obviously not feasible

Then it analyzes greed. Although it is feasible, it is often not the optimal solution, but the approximate optimal solution, which is also not feasible

Therefore, dp problem is a bit like dfs or bfs or greedy problem, but it can not be well solved, and it can be expressed by set method. It is basically dp problem

When do I use dp?

1. The problem can be solved by dfs or bfs, but the problem cannot be solved successfully (pay special attention to the data range)

2. Find some attributes of finite sets, such as the most value (such as: most, least, value, etc.)

3. Be able to use a group of numbers to represent the state. For example, f (i, j) in this question represents the maximum value when the maximum volume of the first i items is j

dp problem analysis method:

Step 1: state representation (generally two-dimensional):

(1) Specify what is required: what is the limiting condition (Volume V), what is required by the topic (maximum value), and what we should do (select some items to obtain the maximum value within the limiting conditions)

(2) Set, our operation on this group of data can be expressed as a set, expressed by f(i, j). Each set can be divided into two subsets f (i-1, J) and f (i-1, J-A (I)). The popular point is that there are two ways to go after the first i - 1 data operation (that is, the question of whether to choose or not), do not choose the i-th or i-th

(3) Operation, f(i, j) the choice to be made here is whether to operate i under the condition that the limiting conditions are met.

(4) f(i, j) represents the operation set of the first i items, and it is also the record of the optimal operation.

Step 2: status calculation:

With the foreshadowing of the first step, we can see that when calculating f(i, j), what we need to do is to find the optimal solution max (f (i-1, J), f (i-1, j-value (I))) when the first I items are selected when the limiting conditions are met; Where f(i - 1, j) represents the optimal choice when the i-th part is not selected and the total volume is j; f(i - 1, j - value(i)) refers to the optimal selection of the ith article with a total volume of J (note that this step is to meet the limiting conditions).

From this, we can get the core idea of dp problem: state transition

If (satisfy condition) f(i, j) = max(f(i - 1, j), f(i - 1, j - value(i)))

Give Code:

#include<iostream>

using namespace std;

const int N = 1010;

int f[N][N];
pair<int, int> b[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for(int i = 1; i <= n; i ++)
        cin >> b[i].first >> b[i].second;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= v; j ++)
        {
            if(b[i].first <= j)
                f[i][j] = b[i].second + f[i - 1][j - b[i].first];
            f[i][j] = max(f[i][j], f[i - 1][j]);
        }
    cout << f[n][v];
    return 0;
}
//f[i][j] = value when the ith item is selected and the volume is j

Here we can carry out one-step optimization, similar to rolling array. It can be seen that the result f(i, j) obtained each time is based on the calculation of f(i - 1, * *), so we can remove a layer of F and change some places to make it equivalent to the original code.

Observe the core part

for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= v; j ++)
        {
            if(b[i].first <= j)
                f[i][j] = b[i].second + f[i - 1][j - b[i].first];
            f[i][j] = max(f[i][j], f[i - 1][j]);
        }

After removing layer i, you can see

for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= v; j ++)
        {
            if(b[i].first <= j)
                f[j] = b[i].second + f[j - b[i].first];
                //f[i][j] = b[i].second + f[i - 1][j - b[i].first];
            f[j] = max(f[j], f[j]);
            //f[i][j] = max(f[i][j], f[i - 1][j]);
        }

Conduct analysis:

f[j] = b[i].second + f[j - b[i].first];
//In cycle I, the equal sign is followed by B [i] second + f[i][j - b[i]. first]
//It is not equivalent to the equivalence before modification, but it can be equivalent if j is cycled from back to front
f[j] = max(f[j], f[j]);
//This sentence is useless

The code can then be reduced to:

for(int i = 1; i <= n; i ++)
        for(int j = v; j; j --)
            if(b[i].first <= j)
                f[j] = b[i].second + f[j - b[i].first];

Final code:

#include<iostream>

using namespace std;

const int N = 1010;

int f[N];
pair<int, int> b[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for(int i = 1; i <= n; i ++)
        cin >> b[i].first >> b[i].second;
    for(int i = 1; i <= n; i ++)
        for(int j = v; j; j --)
            if(b[i].first <= j)
                f[j] = max(f[j], b[i].second + f[j - b[i].first]);
    cout << f[v];
    return 0;
}
//f[i][j] = value when the ith item is selected and the volume is j