Article directory
- 1. Introduction to the idea of moving rules
- 2. Complete backpack [template]
- 3. Change exchange
- 4. Change exchange Ⅱ
- 5. Perfect square numbers
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 dynamic rules blog and the 01 backpack blog before you can read the complete backpack blog, or you already know the dynamic rules 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 complete knapsack problem. The optimization method is written in the template question, and thereafter it is written directly in the code.
2. Complete backpack [template]
DP42 [Template] Complete Backpack
Different from the 01 backpack, a complete backpack can be selected multiple times. dp[i][j] means selecting from the previous i items, the total volume does not exceed j, and the maximum value among all selection methods.
The last position i, if not selected, then look at dp[i – 1][j], if you select 1, then look at dp[i – 1][j – v[i]] + w[i], If you choose 2, then look at dp[i – 1][j – 2v[i]] + 2w[i], and so on. Here only j and the following w have changed, then write dp according to this formula The value of [i][j – v[i]] can finally be obtained through mathematical calculation: dp[i][j] = max(dp[i – 1][j], dp[i][j – v[i ]] + w[i]).
During initialization, the new row and column are all 0. Fill in from top to bottom, left to right, and the return value is dp[n][V].
Then ask the second question and make adjustments based on the above. dp[i][j] means that the volume must be equal to j. According to the previous idea, dp[i][j] = -1 means that this situation does not exist and the requirements cannot be met. During initialization, dp[0][0] = 0, the remaining positions in the first row are -1, and the first column is still 0.
#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 = 0; j <= V; j + + )
{<!-- -->
dp[i][j] = dp[i - 1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
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 = 0; j <= V; j + + )
{<!-- -->
dp[i][j] = dp[i - 1][j];
if(j >= v[i] & amp; & amp; dp[i][j - v[i]] != -1)
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}
Use rolling arrays for optimization. Unlike the 01 backpack, it does not need to cycle from right to left. One of its positions requires a position to the left and a position above the peer. The position of the peer must be updated.
#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[i]; j <= V; j + + )
{<!-- -->
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V] << endl;
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[i]; j <= V; 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;
}
There is another optimization
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[i]; j <= V; 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;
There is an if judgment here to make this dp value available, and then compare it + w[i] and dp[j]. We can make each value in the dp table small enough, so that even if dp[j – v[i]] participates in the comparison and will not be used.
memset(dp, 0, sizeof(dp));
for(int j = 1; j <= V; j + + ) dp[j] = -0x3f3f3f3f;//Half of INT_MIN, which is small enough.
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = v[i]; j <= V; j + + )
{<!-- -->
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << (dp[V] < 0 ? 0 : dp[V]) << endl;
3. Change exchange
322. Change exchange
dp[i][j] means selecting from the first i coins, the total amount is exactly equal to j. Among all selection methods, the minimum number of coins, j is the amount.
The last position i, if not selected, look at dp[i – 1][j]. If you choose i and choose 1, then the value of this coin is coins[i]. In order to reach j without exceeding it, you have to look at dp[i – 1][j – coins[i]], and then + 1 , because what is stored is a number. If you choose 2, then it is dp[i – 1][j – 2coins[i]] + 2. According to the previous mathematical calculation, if you choose i, it is dp[i][j – coins [i]] + 1, and then take the smaller value of dp[i – 1][j].
During initialization, add one more row and one column, dp[0][0] is 0, and other positions in the first row are invalid, because it is impossible to make up the amount without coins. According to the previous optimization, it was originally set to -1 and then judged, here Just initialize it to a large enough number, because this question is min, initialize it to 0x3f3f3f3f.
Returns the value of the last position, but it may not be possible in the end, so you have to make a final judgment. and scrolling array optimization.
int coinChange(vector<int> & amp; coins, int amount) {<!-- -->
const int INF = 0x3f3f3f3f;
int n = coins.size();
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = coins[i - 1]; j <= amount; j + + )
{<!-- -->
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
}
}
return dp[amount] >= INF ? -1 : dp[amount];
}
4. Change Exchange II
518. Change Exchange II
After reading the ideas of the previous question, the answer to this question came out quickly.
Previous question code
int coinChange(vector<int> & amp; coins, int amount) {<!-- -->
const int INF = 0x3f3f3f3f;
int n = coins.size();
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = coins[i - 1]; j <= amount; j + + )
{<!-- -->
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
}
}
return dp[amount] >= INF ? -1 : dp[amount];
}
Now the number of combinations is required, so + 1 is not needed when selecting i. There is no need to find min, but all possible values are added up. According to the optimized code, dp[j] = dp[j] + dp[j – coins[i]]. There is no need to judge when returning, and the last position is returned directly. The value is enough.
int change(int amount, vector<int> & amp; coins) {<!-- -->
int n = coins.size();
vector<int> dp(amount + 1);
dp[0] = 1;
for(int i = 1; i <= n; i + + )
{<!-- -->
for(int j = coins[i - 1]; j <= amount; j + + )
{<!-- -->
dp[j] + = dp[j - coins[i - 1]];
}
}
return dp[amount];
}
5. Perfect square numbers
279. Perfect square numbers
It is also a complete knapsack problem. dp[i][j] means selecting from the first i perfect square numbers. The sum is exactly equal to j, which is the smallest number among all selection methods.
Analyze the interval from 1 to i square. If you don’t choose i square, then look at dp[i – 1][j]. If you choose an i square, then look at dp[i – 1][j – i^2] + 1. Choose two i-squares, the same as before. The final result is dp[i][j – i^2] + 1, and then take min from the two numbers.
During initialization, dp[0][0] is 0, and the rest of the first row does not exist, so it is also set to the special value 0x3f3f3f3f. The first column is ignored and the default is 0.
The return value is dp[root n][n].
int numSquares(int n) {<!-- -->
int m =sqrt(n);
vector<int> dp(n + 1, 0x3f3f3f3f);
dp[0] = 0;
for(int i = 1; i <= m; i + + )
{<!-- -->
for(int j = i * i; j <= n; j + + )
{<!-- -->
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
Finish.