Opening question:
There are n items, weight = {7,2,4,6} backpack weight limit g =11
The backpack can be loaded into the maximum weight.
The whole solution process is divided into n stages, and each stage decides whether an item can be put into the backpack. The total weight of the pack varies at the end of each stage.
Use a two-dimensional array Boolean [][] States [I][j] to indicate whether the pack can be loaded in phase I when the total weight of the pack is J. 0<= i < n and 0 <= j <=g
In the 0 stage (subscript 0), the weight is 7, and there are two decision-making results, either put in or not put in. The weight of the corresponding backpack has two states, 0 or 7, which are both smaller than 11. The corresponding states are expressed as States [0][0] = true, and States [0][7] = true
In the first stage (subscript 1), the weight is 2. Based on the decision result of the previous stage, after the decision of this item is made, the backpack has four states. The first two are to keep the original backpack state without adding 0(0+0) and 7(7+0), and the last two are to add 9(7+2) and 2(0+2), both smaller than 11. States [1][0] = True, States [1][7] = True, States [1][9] = True, and States [1][2] = True
At the second stage (subscript 2), the weight is 4. After the item decision is made, the backpack has eight states. The first four states are to keep the original backpack state without adding 0(0+0+0), 7(7+0+0), 9(7+2+0), 2(0+2+0), and the last four states are to add to the backpack, 4(0+0+4), 11(7+0+4), 13(7+2+4),6(0+2+4), where 13 is larger than 11, overweight, ignored. States [2][0] = true, States [2][7] = true, States [2][9] = true, States [2][2] = True, States [2][4] = True, States [2][11] = True, states[2][6] = True
The next calculation, stage 3, and so on, has 16 cases, where the overweight are ignored, and the other states are recorded.
States [I][j] = true, which is the maximum weight that the backpack can carry.
Draw a picture and reason as follows:
When drawing the state table, each stage is filled with an obvious feature. Copy over the state of the previous stage first, and then add your weight to the backpack on the basis of the previous stage.
The state transition equation can be deduced as
states[i][j] ===>> { states[i-1][j] || states[i-1][j-weight[i] }
Code explanation:
public int dpackage(int[] weight, int n, int g) { boolean[][] states = new boolean[n][g+1]; State [0][0] = true; state [0] = true; if (weight[0] <= g) { states[0][weight[0]] = true; } for (int i = 1; i < n; ++ I) {// int tmpW = weight[I]; for (int j = 0; j <= g; + + j) {/ / don't put the ith a item in the backpack if (states) [j] [I - 1] states [I] [j] = states [I] [j] | | states [j] [I - 1]. If (j +tmpW <= g&& States [i-1][j]){states[I][j+tmpW] = true; For (int I = g; i >= 0; --i) { if (states[n - 1][i]) return i; } return 0; }Copy the code
This is an opportunity to introduce three features of dynamic programming
Dynamic programming has three features
- Optimal substructure
The optimal solution of the problem contains the optimal solution of the subproblem, and the state of the later stages can be deduced from the preceding.
The optimal solution of each stage has been solved in the solution, and the decision of the later stage needs to be made on the basis of the previous results.
- There was no aftereffect
I don’t care how it was derived, once the current state is determined, it won’t be affected by subsequent decisions.
- Repeating subproblem
When different decision sequences reach the same stage, they may produce repeated states.
This should be best understood by the comparison of recursive solutions, there are many times of repeated calculation, while dynamic programming records the decision results at each stage, there is no double calculation.
Advanced question type:
1 determine whether a specific total weight can be stored in the backpack
Example: Leetcode 416 split array
Leetcode-cn.com/problems/pa…
Target = sum /2
States [n-1][target]
int len = nums.length; if (len == 0) { return false; } int sum = 0; for (int num : nums) { sum += num; If ((sum & 1) == 1) {return false; } int g = sum / 2; Boolean [][] states = new Boolean [len][g + 1]; State [0][0] = true; If (nums[0] <= g) {states[0][nums[0]] = true; } for (int I = 1; i < len; i++) { for (int j = 0; j <= g; J++) {/ / don't put the ith a item in the backpack if (states) [j] [I - 1] states [I] [j] = states [I] [j] | | states [j] [I - 1]. / / put the ith a item in the backpack if (j + nums [I] < = g && states [I - 1] [j]) {states [I] [j + nums [I]] = true; }}} // Return states[len-1][g];Copy the code
2 Every item has value, seek maximum value
Solution: Add a value variable on the basis of the first question type, and ask to find the maximum value of the backpack.
The only difference is that states[I][j] is no longer a Boolean value stored in the two-dimensional array, but the maximum value corresponding to the backpack weight of J in the current decision stage.
The result is to find the maximum value, traversing the last layer of n-1.
public static int knapsack3(int[] weight, int[] value, int n, int w) { int[][] states = new int[n][w + 1]; for (int i = 0; i < n; ++ I) {// Initialize states for (int j = 0; j < w + 1; ++j) { states[i][j] = -1; } } states[0][0] = 0; if (weight[0] <= w) { states[0][weight[0]] = value[0]; } for (int i = 1; i < n; For (int j = 0; j <= w; + + j) {if (states [j] [I - 1] > = 0) {/ / not to choose the ith items states [I] [j] = math.h Max (states [j], [I] states [j] [I - 1]). If (j + weight[I] <= w) {states[I][j + weight[I]] = states[i-1][j] + value[I]; }}}} // find the maximum value int maxValue = -1; for (int j = 0; j <= w; ++j) { if (states[n - 1][j] > maxvalue) maxvalue = states[n - 1][j]; } return maxvalue; }Copy the code
Find the maximum value at a given weight
On the basis of the second question type, find the maximum value of a certain weight. The leetcode 494 goal is similar to this, except that the two-dimensional array stores the number of combinations, not the maximum value. If you’re interested, take a look.
Leetcode-cn.com/problems/ta…
4 Other Deformation
On the basis of 0-1 knapsack, the combination number, the minimum number of items used, etc., can be in the above ideas, change the two-dimensional array type, thinking.
5 Complete backpack problem
Items can be placed in the backpack multiple times.
Leetcode 322 change for leetcode-cn.com/problems/co…
Leetcode 518 change combination number leetcode-cn.com/problems/co…
This state transfer equation is different from the 0-1 backpack in that it depends not only on the result of the previous decision stage, but also on the j-weight [I] state of the backpack at the same stage.
In the form of state transition states [I] [j] = = = > > states [j], [I – 1] states [I] [j – weight [I]]
322 Change
class Solution { public int coinChange(int[] coins, int amount) { int[][] dp = new int[coins.length][amount+1]; Arrays.sort(coins); for(int k=1; k<=amount; k++){ dp[0][k] = Integer.MAX_VALUE; // Initialize if(coins[0] <= k && dp[0][k-coins[0]]! = Integer.MAX_VALUE){ dp[0][k] = dp[0][k-coins[0]] +1; } } for(int i=1; i<coins.length; i++){ for(int j=1; j<=amount; j++){ int temp = Integer.MAX_VALUE; if(coins[i] <= j && dp[i][j-coins[i]] ! = Integer.MAX_VALUE){ temp = dp[i][j-coins[i]] +1; } dp[i][j] = Math.min(temp,dp[i-1][j]); } } return dp[coins.length-1][amount] == Integer.MAX_VALUE ? -1 : dp[coins.length - 1][amount]; }}Copy the code
conclusion
Backpack series from simple to difficult, a series of conditions added step by step, the actual leetcode dynamic programming topics are derived from a lot of. If you can master this sequence, you will have a logical model in your mind.
Personal habit of solving problems
Backtracking -> state transition table method
When I encounter some tricky problems of dynamic programming, I will try to write the code of recursive backtracking first, feeling that this is easier to be accepted by my stupid head, and then derive the state transition equation of dynamic programming
Domain modeling, abstract thinking.
It is very important to understand the topic, to model the domain, and to translate it into an understandable or familiar way of thinking. Pull out, resolve the meaning of the topic, you can draw inferential conclusions, get twice the result with half the effort.
Sometimes the Angle of the answer is hard to come up with. The so-called standing Angle is different, see the scenery is different, of course, the train of thought will be different. But usually can have a look, learn to learn, broaden thinking, when the problem is good spring thought gushing ah. 😊