|
1 | 1 | M |
2 | | -1517903196 |
3 | | -tags: DP |
4 | | - |
5 | | -考虑: 用i个item (可跳过地取), 是否能装到weight w? |
6 | | -需要从'可能性'的角度考虑, 不要搞成单一的最大值问题. |
7 | | - |
8 | | -1. 背包可装的物品大小和总承重有关. |
9 | | -2. 不要去找dp[i]前i个物品的最大总重, 找的不是这个. |
| 2 | +1524200994 |
| 3 | +tags: DP, Backpack DP |
| 4 | + |
| 5 | +给i本书, 每本书有自己的重量 int[] A, 背包有自己的大小M, 看最多能放多少重量的书? |
| 6 | + |
| 7 | +#### Backpack DP 1 |
| 8 | +- 简单直白的思考 dp[i][m]: 前i本书, 背包大小为M的时候, 最多能装多种的书? |
| 9 | +- **注意**: 背包问题, 重量weight一定要是一维. |
| 10 | +- dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]); |
| 11 | +- 每一步都track 最大值 |
| 12 | +- 最后return dp[n][m] |
| 13 | +- 时间空间 O(mn) |
| 14 | +- Rolling array, 空间O(m) |
| 15 | + |
| 16 | +#### Backpack DP 2 |
| 17 | +- true/false求解, 稍微曲线救国: 重点是, 最后, 按照weight从大到小遍历, 第一个遇到true的, index就是最大值. |
| 18 | +- 考虑: 用i个item (可跳过地取), 是否能装到weight w? |
| 19 | +- 需要从'可能性'的角度考虑, 不要搞成单一的最大值问题. |
| 20 | +- 1. 背包可装的物品大小和总承重有关. |
| 21 | +- 2. 不要去找dp[i]前i个物品的最大总重, 找的不是这个. |
10 | 22 | dp[i]及时找到可放的最大sum, 但是i+1可能有更好的值, 把dp[i+1]变得更大更合适. |
11 | 23 |
|
12 | | -boolean[][] dp[i][j]表示: 有前i个item, 用他们可否组成size为j的背包? true/false. |
13 | | -(反过来考虑了，不是想是否超过size j, 而是考虑是否能拼出exact size == j) |
14 | | -**注意**: 虽然dp里面一直存在i的位置, 实际上考虑的是在i位置的时候, 看前i-1个item. |
15 | | - |
16 | | -多项式规律: |
17 | | -1. picked A[i-1]: 就是A[i-1]被用过, weight j 应该减去A[i-1]. 那么dp[i][j]就取决于dp[i-1][j-A[i-1]]的结果. |
18 | | -2. did not pick A[i-1]: 那就是说, 没用过A[i-1], 那么dp[i][j]就取决于上一行d[i-1][j] |
19 | | -dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]] |
| 24 | +##### 做法 |
| 25 | +- boolean[][] dp[i][j]表示: 有前i个item, 用他们可否组成size为j的背包? true/false. |
| 26 | +- (反过来考虑了，不是想是否超过size j, 而是考虑是否能拼出exact size == j) |
| 27 | +- **注意**: 虽然dp里面一直存在i的位置, 实际上考虑的是在i位置的时候, 看前i-1个item. |
20 | 28 |
|
21 | | -结尾: |
22 | | -跑一遍dp 最下面一个row. 从末尾开始找, 最末尾的一个j (能让dp[i][j] == true)的, 就是最多能装的大小 :) |
| 29 | +##### 多项式规律 |
| 30 | +- 1. picked A[i-1]: 就是A[i-1]被用过, weight j 应该减去A[i-1]. 那么dp[i][j]就取决于dp[i-1][j-A[i-1]]的结果. |
| 31 | +- 2. did not pick A[i-1]: 那就是说, 没用过A[i-1], 那么dp[i][j]就取决于上一行d[i-1][j] |
| 32 | +- dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]] |
23 | 33 |
|
24 | | -时间，空间都是：O(mn) |
| 34 | +##### 结尾 |
| 35 | +- 跑一遍dp 最下面一个row. 从末尾开始找, 最末尾的一个j (能让dp[i][j] == true)的, 就是最多能装的大小 :) |
| 36 | +- 时间，空间都是：O(mn) |
25 | 37 |
|
26 | 38 |
|
27 | 39 | ``` |
|
49 | 61 |
|
50 | 62 |
|
51 | 63 | */ |
| 64 | + |
| 65 | +/* |
| 66 | +Thoughts: |
| 67 | +Backpack problem, always consider a dimension with weight/size. |
| 68 | +int dp[i][j]: with i items and backpack size/weight-limit of j, what's max weight can we put in? |
| 69 | +
|
| 70 | +dp[i][j] depends on last item's size && what's the state with [i-1] items. |
| 71 | +
|
| 72 | +dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]); |
| 73 | +
|
| 74 | +dp[0][0] = 0; no book, 0 weight limit |
| 75 | +dp[0][j] = 0; no book, can't fill bag |
| 76 | +dp[i][0] = 0; i books, but weight-limit = 0, can't fill |
| 77 | +*/ |
| 78 | +public class Solution { |
| 79 | + public int backPack(int m, int[] A) { |
| 80 | + if (A == null || A.length < 0) { |
| 81 | + return 0; |
| 82 | + } |
| 83 | + int n = A.length; |
| 84 | + int[][] dp = new int[n + 1][m + 1]; |
| 85 | + |
| 86 | + // Calculcate possibility for i items to fill up w weight |
| 87 | + for (int i = 1; i <= n; i++) { |
| 88 | + for (int j = 0; j <= m; j++) { |
| 89 | + // default: item(i-1) not used: |
| 90 | + dp[i][j] = dp[i - 1][j]; |
| 91 | + if (j - A[i - 1] >= 0) { // possible to use item(i-1) |
| 92 | + dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]); // use item(i-1) |
| 93 | + } |
| 94 | + } |
| 95 | + } |
| 96 | + |
| 97 | + return dp[n][m]; |
| 98 | + } |
| 99 | +} |
| 100 | + |
| 101 | +// Rolling array |
| 102 | +public class Solution { |
| 103 | + public int backPack(int m, int[] A) { |
| 104 | + if (A == null || A.length < 0) { |
| 105 | + return 0; |
| 106 | + } |
| 107 | + int n = A.length; |
| 108 | + int[][] dp = new int[2][m + 1]; |
| 109 | + |
| 110 | + // Calculcate possibility for i items to fill up w weight |
| 111 | + for (int i = 1; i <= n; i++) { |
| 112 | + for (int j = 0; j <= m; j++) { |
| 113 | + // default: item(i-1) not used: |
| 114 | + dp[i % 2][j] = dp[(i - 1) % 2][j]; |
| 115 | + if (j - A[i - 1] >= 0) { // possible to use item(i-1) |
| 116 | + dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + A[i - 1]); // use item(i-1) |
| 117 | + } |
| 118 | + } |
| 119 | + } |
| 120 | + return dp[n % 2][m]; |
| 121 | + } |
| 122 | +} |
| 123 | + |
52 | 124 | /* |
53 | 125 | Thoughts: |
54 | 126 | DO NOT try to find the maxSum using given values: this approach f[i] only returns max sum, |
|
0 commit comments