Article directory
- 1. Introduction to the idea of moving rules
- 2. Template question: 01 Backpack
-
- First question
- Second question
- optimization
- 3. Split equal-sum subsets
- 4. Goals and
- 5. The weight of the last stone Ⅱ
The knapsack problem requires readers to first understand what dynamic programming is and understand the ideas of dynamic programming, which cannot be taught to those who are new to dynamic programming. Therefore, it is best to read the previous blogs about kungfu before you can read all the blogs about backpack issues, or you already know kungfu yourself.
1. Introduction to dynamic rules
The idea of moving rules has five steps, and it is best to draw pictures to understand the details, don’t be afraid of trouble. When you start drawing pictures and read the questions carefully, you will experience the immersion in learning.
Status representation
state transition equation
initialization
Order of filling in the form
return value
Generally, dynamic rules will first create an array named dp. This array is also called dp table. Through some operations, the dp table is filled, and one of the values is the answer. Each element of the dp array indicates a state. Our first step is to determine the state.
The status may be determined through the question requirements, the status may be determined through experience + question requirements, or the status may be determined by repeated sub-problems discovered during the analysis process. There are other ways to determine the status, but they are all similar. Once you understand the rules of movement, these ideas will also arise. The determination of the status is to determine what dp[i] is intended to represent. This is the most important step. The status representation is usually determined by using a certain position as the end or starting point.
The state transition equation is what dp[i] is equal to, and what the state transition equation is. Like the Fibonacci sequence, dp[i] = dp[i – 1] + dp[i – 2]. This is the hardest step. At the beginning, the state representation may be incorrect, but it doesn’t matter. Make the state boldly. If the transfer equation cannot be derived and the result cannot be obtained, then the state representation is wrong. Therefore, state representation and state transition equations complement each other and can help you check your ideas.
To determine the equation, divide the problem from the nearest step.
Initialization means filling in the form to ensure that it does not cross the boundary. As mentioned in the first paragraph, the rule of thumb is to fill out a form. For example, in the Fibonacci sequence, if we want to fill in dp[1], then we may need dp[0] and dp[-1], which is out of bounds, so in order to prevent out of bounds, the first two values are fixed at the beginning. , then the third value is the sum of the first two values, and there will be no out-of-bounds. There are more ways to initialize than this. There are some problems. If a position is obtained from the first two positions, if we initialize the first two positions and then write the code, we will find that it is not efficient enough. At this time, You need to set up a virtual node. For a one-dimensional array, fill in another position to the left of position 0 in the array. The number of elements in the entire dp array is also + 1, so that the original dp[0] becomes the current one. dp[1], the two-dimensional array needs to fill in one column and one row. After setting all the values of this row and column, the first column and first row of the original array can be initialized by filling in the new ones. This initialization method is as follows Gradually understand it through problem solving.
The considerations for the second initialization method are how to initialize the value of the virtual node to ensure that the result of filling the table is correct, and to maintain the mapping relationship between the new table and the old table, that is, the change of the subscript.
The order of filling in the forms. When filling in the current status, the required status should have been calculated. It is still the Fibonacci sequence. When filling in dp[4], dp[3] and dp[2] should have been calculated, and then dp[4] will come out. The order at this time is from left to right. . There are other sequences, which should be decided based on the previous analysis.
The return value depends on the question requirements.
There are many classifications of knapsack problems. This article is about the 01 knapsack problem. The knapsack problem needs to be optimized after the code is written. Therefore, compared with the previous blogs on dynamic algorithms, several blogs on the knapsack problem all add a step of optimization at the end. But the optimization method is only inscribed in the template, and nothing else is written.
2. Template question: 01 Backpack
DP41 [Template] 01 Backpack
First question
First, set dp[i] as the i items in the past, and select the one with the highest value. This is actually not possible. If you want to select the i-th item, you need to check whether the backpack is full, but the current state cannot express the volume. , so no. Then use a two-dimensional array. dp[i][j] represents the maximum value that can be selected from the first i items, with the total volume not exceeding j, among all selection methods.
State transition equation. Analyze based on the last step. We can choose the i-th item or not. If you do not choose, you will choose from 0 to i- 1, and the result of this is placed in dp[i -1][j]; if you choose the element at position i, that is, the volume plus vi, then in order not to exceed the backpack, just You have to choose the value of the position dp[i – 1][j – vi] plus wi. There is another consideration in this situation. Maybe vi is greater than j, so j – vi needs to be >= 0. So dp[i][j] = max(dp[i – 1][j – 1], dp[i – 1][j – vi] + wi).
For initialization, add a row and a column, and the values inside are all 0. The return value is the maximum value.
Second question
Make changes based on the first question. The previous dp[i][j] should be changed from never exceeding j to exactly equal to j. In the state transition equation, it is possible that after selecting one, it is still not enough. If you do not choose the i-th item, then it is dp[i – 1][j], which means that if you choose the first i – 1 item, the volume is equal to the maximum value of j, but it may not reach j. Let’s first Define dp[i][j] = -1 to indicate that there is no such situation, that is, there is no selection method that can reach volume j among the first i items. If dp[i – 1][j] is -1, then the volume of the item at position i will still not reach j if it is not selected, so there is no need to consider it if it is not selected. If you select the i-th item, you must first check whether dp[i – 1][j – vi] exists, which is not equal to -1. That is to say, the first i – 1 position has exactly reached the volume of j – vi. Then adding the i-th item is feasible.
initialization. When adding new rows and columns, the first column is all 0, and the rest of the first row is -1.
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main()
{<!-- -->
cin >> n >> V;
for(int i = 1; i <= n; i + + )
{<!-- -->
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = 1; j <= V; j + + )
{<!-- -->
dp[i][j] = dp[i - 1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;//First question
memset(dp, 0, sizeof(dp));
for(int j = 1; j <= V; j + + ) dp[0][j] = -1;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = 1; j <= V; j + + )
{<!-- -->
dp[i][j] = dp[i - 1][j];
if(j >= v[i] & amp; & amp; dp[i - 1][j - v[i]] != -1) dp[i][j] = max(dp[i][j ], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}
Optimization
The array is very large, so use the idea of rolling the array to optimize it. Take a closer look at the analysis. dp[i][j] is determined by dp[i – 1][j] and dp[i – 1][j – vi]. That is, one element of this row is determined by two elements of the previous row. It is determined by elements and has nothing to do with other rows. Then we only need two rows to complete the filling of the dp table. After filling in the second row based on the first row, the first row will be used as the original second row. Continue updating the data as a new second row. This is the scrolling array. But it can also reduce space. Use only one line to do this. dp[j] is determined by dp[j] and dp[j – vi], and then updates dp[j]. If one line is used, the order of filling in the table cannot be from left to right, because dp[j – vi] will change dp [j – vi] are replaced, so the order of filling in the form should be from right to left to ensure that each value is updated correctly.
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main()
{<!-- -->
cin >> n >> V;
for(int i = 1; i <= n; i + + )
{<!-- -->
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = V; j >= v[i]; j--)//Originally j >= 1, judged below, but in fact it can be placed directly in for brackets to reduce the number of loops
{<!-- -->
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;//First question
memset(dp, 0, sizeof(dp));
for(int j = 1; j <= V; j + + ) dp[j] = -1;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = V; j >= v[i]; j--)
{<!-- -->
if(dp[j - v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
3. Split equal sum subsets
416. Split equal sum subsets
It can be converted into selecting a number to meet the condition of being half of the sum of the entire array. Moreover, in fact, it is to select from the previous i numbers. Among all the selection methods, can the number j be collected? The type is bool, and j is sum / 2.
State transition equation. If you do not select i, then look at dp[i – 1][j]; if you select i, then add the previous value to the value of the i position. Assuming that the previous value is numi, then this position should be at the j – numi position. , but j-numi must exist.
Initialization adds a row and a column, the first column is true, and the rest of the first row is false.
The return value is dp[n][sum / 2].
bool canPartition(vector<int> & amp; nums) {<!-- -->
int n = nums.size(), sum = 0;
for(auto x : nums) sum + = x;
if(sum % 2) return false;
int aim = sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(aim + 1));
for(int i = 0; i <= n; i + + ) dp[i][0] = true;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = 1; j <= aim; j + + )
{<!-- -->
dp[i][j] = dp[i - 1][j];
if(j >= nums[i - 1])
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
return dp[n][aim];
}
But this approach is really inappropriate. Optimize it according to the rolling array.
bool canPartition(vector<int> & amp; nums) {<!-- -->
int n = nums.size(), sum = 0;
for(auto x : nums) sum + = x;
if(sum % 2) return false;
int aim = sum / 2;
vector<bool> dp(aim + 1);
dp[0] = true;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = aim; j >= nums[i - 1]; j--)
{<!-- -->
dp[j] = dp[j] || dp[j - nums[i - 1]];
}
}
return dp[aim];
}
4. Goal and
494. Goals and
According to the question, these numbers will be divided into positive numbers and negative numbers. Assume that the positive number is a and the absolute value of the negative number is b, that is, a + b = sum, a – b = target, so a = (t + s) / 2. At this time b disappears. Then just look at a, that is to say, choose some numbers, and the sum is exactly a. How many choices are there, that is the answer. dp[i][j] means how many choices there are to choose from the previous i numbers, and the sum is exactly equal to i.
State transition equation. If i is selected, then look at dp[i – 1][j nums[i]]. Because it is the number of methods, there is no need for + nums[i]; if i is not selected, look at dp[i – 1][ j].
During initialization, the new rows and columns are all 0, except that dp[0][0] is 1.
The return value is the last value. The optimization part is written directly into the code.
int findTargetSumWays(vector<int> & amp; nums, int target) {<!-- -->
int sum = 0;
for(auto x: nums) sum + = x;
int aim = (sum + target) / 2;
if(aim < 0 || (sum + target) % 2) return 0;
int n = nums.size();
vector<int> dp(aim + 1);
dp[0] = 1;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = aim; j >= nums[i - 1]; j--)
{<!-- -->
dp[j] + = dp[j - nums[i - 1]];
}
}
return dp[aim];
}
5. The weight of the last stone II
1049. The weight of the last stone II
Analyze the topic. Every time you get two numbers, do it according to the question. It is actually equivalent to adding a positive number and a negative number to get a value. If it is 0, it will be gone. If there are more elements, it will be similar to the previous question. Operation between a bunch of positive numbers and a bunch of negative numbers. Assume that the positive number is a and the absolute sum of the negative numbers is b, then a + b = sum, find the smallest value of a – b. From the perspective of sum, a number can be divided into two numbers and added. If the two numbers are closer to half of sum, the smaller the difference. So in the end the problem is converted to selecting some numbers in the array so that the sum of these numbers is as close to sum / 2 as possible.
Let dp[i][j] represent the maximum sum selected from the previous i numbers, and the sum does not exceed j. This j is sum/2. If i is selected, it is dp[i – 1][j – nums[i]] + nums[i]. If i is not selected, it is dp[i – 1][j], and then the maximum value is selected.
Initialization, new rows and columns are all 0.
The return value returns sum – 2* dp[n][sum / 2]. Optimization is written directly.
int lastStoneWeightII(vector<int> & amp; stones) {<!-- -->
int sum = 0;
for(auto x : stones) sum + = x;
int n = stones.size(), m = sum / 2;
vector<int> dp(m + 1);
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = m; j >= stones[i - 1]; j--)
{<!-- -->
dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
}
}
return sum - 2 * dp[m];
}
Finish.