GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — leet-code/Java/Backpack.java at master · awangdev/leet-code Expand file tree/ Copy pathBackpack.javaMore file actions executable file ·316 lines (262 loc) · 10.4 KB / Copy pathBackpack.javaFile metadata and controlsexecutable file ·316 lines (262 loc) · 10.4 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 M 1524200994 tags: DP, Backpack DP 给i本书, 每本书有自己的重量 int[] A, 背包有自己的大小M, 看最多能放多少重量的书? #### Backpack DP 1 - 简单直白的思考 dp[i][m]: 前i本书, 背包大小为M的时候, 最多能装多种的书? - **注意**: 背包问题, 重量weight一定要是一维. - dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]); - 每一步都track 最大值 - 最后return dp[n][m] - 时间空间 O(mn) - Rolling array, 空间O(m) #### Backpack DP 2 - true/false求解, 稍微曲线救国: 重点是, 最后, 按照weight从大到小遍历, 第一个遇到true的, index就是最大值. - 考虑: 用i个item (可跳过地取), 是否能装到weight w? - 需要从'可能性'的角度考虑, 不要搞成单一的最大值问题. - 1. 背包可装的物品大小和总承重有关. - 2. 不要去找dp[i]前i个物品的最大总重, 找的不是这个. dp[i]及时找到可放的最大sum, 但是i+1可能有更好的值, 把dp[i+1]变得更大更合适. ##### 做法 - boolean[][] dp[i][j]表示: 有前i个item, 用他们可否组成size为j的背包? true/false. - (反过来考虑了，不是想是否超过size j, 而是考虑是否能拼出exact size == j) - **注意**: 虽然dp里面一直存在i的位置, 实际上考虑的是在i位置的时候, 看前i-1个item. ##### 多项式规律 - 1. picked A[i-1]: 就是A[i-1]被用过, weight j 应该减去A[i-1]. 那么dp[i][j]就取决于dp[i-1][j-A[i-1]]的结果. - 2. did not pick A[i-1]: 那就是说, 没用过A[i-1], 那么dp[i][j]就取决于上一行d[i-1][j] - dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]] ##### 结尾 - 跑一遍dp 最下面一个row. 从末尾开始找, 最末尾的一个j (能让dp[i][j] == true)的, 就是最多能装的大小 :) - 时间，空间都是：O(mn) ``` /* Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack? Example If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack. You function should return the max size we can fill in the given backpack. Note You can not divide any item into small pieces. Challenge O(n x m) time and O(m) memory. O(n x m) memory is also acceptable if you do not know how to optimize memory. Tags Expand LintCode Copyright Dynamic Programming Backpack */ /* Thoughts: Backpack problem, always consider a dimension with weight/size. int dp[i][j]: with i items and backpack size/weight-limit of j, what's max weight can we put in? dp[i][j] depends on last item's size && what's the state with [i-1] items. dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]); dp[0][0] = 0; no book, 0 weight limit dp[0][j] = 0; no book, can't fill bag dp[i][0] = 0; i books, but weight-limit = 0, can't fill */ public class Solution { public int backPack(int m, int[] A) { if (A == null || A.length < 0) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; // Calculcate possibility for i items to fill up w weight for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // default: item(i-1) not used: dp[i][j] = dp[i - 1][j]; if (j - A[i - 1] >= 0) { // possible to use item(i-1) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + A[i - 1]); // use item(i-1) } } } return dp[n][m]; } } // Rolling array public class Solution { public int backPack(int m, int[] A) { if (A == null || A.length < 0) { return 0; } int n = A.length; int[][] dp = new int[2][m + 1]; // Calculcate possibility for i items to fill up w weight for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // default: item(i-1) not used: dp[i % 2][j] = dp[(i - 1) % 2][j]; if (j - A[i - 1] >= 0) { // possible to use item(i-1) 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) } } } return dp[n % 2][m]; } } /* Thoughts: DO NOT try to find the maxSum using given values: this approach f[i] only returns max sum, but does not guarantee to pick the most sutible items that maximize f[n]. 1. Always consider weight 2. Consider it as a possibility problem based on weight 0 ~ m Using given items, can we fill backpack with size 0, size 1, size 2... size m - 1, and size m? We save these values with boolean dp[i][w]: using i items to fill size w, where i is the A index. Two conditions for calculating dp[i][w] 1. i - 1 items filled up w, so dp[i][w] = dp[i - 1][w]. No need to add A[i - 1]. 2. i - 1 items fileld up w - A[i - 1]; once adding A[i - 1], it'll fill up w. dp[i][w] = dp[i - 1][w - A[i - 1]], so we are counting on if i - 1 items filled up weight: w - A[i - 1]. We'll loop over j = 1 ~ m, and attempt to fill all sizes with i items. init: dp[0][0]: using 0 items to fill 0 space, sure. True. dp[0][1~m]: using 0 items to fill 1~m space, not gonna work. False. */ public class Solution { public int backPack(int m, int[] A) { if (A == null || A.length < 0) { return 0; } int n = A.length; boolean[][] dp = new boolean[n + 1][m + 1]; // weight 0 is a valid value. // items does not have 0's item, so we need to init dp based for all entries where i == 0 dp[0][0] = true; for (int j = 1; j <= m; j++) { dp[0][j] = false; } // Calculcate possibility for i items to fill up w weight for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // default: item(i-1) not used: dp[i][j] = dp[i - 1][j]; if (j - A[i - 1] >= 0) { // possible to use item(i-1) dp[i][j] |= dp[i - 1][j - A[i - 1]]; // use item(i-1) } } } // Find max weight size that makes dp[i][j] true for (int j = m; j >= 0; j--) { if (dp[n][j]) { return j; } } return 0; } } /* Thoughts: rolling array. Always use i, and i - 1 dp. can replace the two index with curr, pre */ public class Solution { public int backPack(int m, int[] A) { if (A == null || A.length < 0) { return 0; } int n = A.length; boolean[][] dp = new boolean[2][m + 1]; int curr = 0; int pre = 1; // weight 0 is a valid value. // items does not have 0's item, so we need to init dp based for all entries where i == 0 dp[curr][0] = true; for (int j = 1; j <= m; j++) { dp[curr][j] = false; } // Calculcate possibility for i items to fill up w weight for (int i = 1; i <= n; i++) { curr = pre; pre = 1 - curr; for (int j = 0; j <= m; j++) { // default: item(i-1) not used: dp[curr][j] = dp[pre][j]; if (j - A[i - 1] >= 0) { // possible to use item(i-1) dp[curr][j] |= dp[pre][j - A[i - 1]]; // use item(i-1) } } } // Find max weight size that makes dp[i][j] true for (int j = m; j >= 0; j--) { if (dp[curr][j]) { return j; } } return 0; } } /* Thoughts: Recap on 12.02.2015 State DP[i][j]: i is the index of Ai, and j is the size from (0 ~ m). It means: depending if we added A[i-1], can we full-fill j-space? Return ture/false. Note: that is, even j == 0, and I have a item with size == 0. There is nothing to add, which means the backpack can reach j == 0. True. However, if we have a item with size == 2, but I need to fill space == 1. I will either pick/not pick item of size 2; either way, can't fill a backpack with size 1. False; Function: DP[i][j] = DP[i - 1][j] || DP[i - 1][j - A[i - 1]]; // based on if previous value is true/false: 1. didn't really add A[i-1] || 2. added A[i-1]. Init: DP[0][0] = true; // 0 space and 0 items, true. All the rest are false; Return the very last j that makes dp[A.length][j] true. */ public class Solution { public int backPack(int m, int[] A) { if (A == null || A.length == 0 || m <= 0) { return 0; } boolean[][] dp = new boolean[A.length + 1][m + 1]; dp[0][0] = true; for (int i = 1; i <= A.length; i++) { for (int j = 0; j <= m; j++) { //j is large enough: if (j - A[i - 1] >= 0) { //not added A[i - 1] or added A[i - 1] dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]]; } else {// j not large enough, ofcourse not adding A[i-1] dp[i][j] = dp[i - 1][j]; } } } //Largest possible size with dp[j] == true for (int j = m; j >= 0; j--) { if (dp[A.length][j]) { return j; } } return 0; } } /* 1D array: memory mxn, space m. Tricky tho ... Looking at the 2D version, we are really just checking the DP with fixed i=A.length. DP[j]: can we fit i items into j? DP[j] == false || DP[j - A[i - 1]]. Similar two cases: 1. Can't fit in, set false; 2. Can fit in, then just return if (j - A[i - 1]) works Core difference: only set the DP[j] when (j - A[i - 1] >= 0 && DP[j - A[i - 1]]): since we are running from m ~ 0, we don't want to override some existing values */ public class Solution { public int backPack(int m, int[] A) { if (A == null || m == 0) { return 0; } boolean[] DP = new boolean[m + 1]; DP[0] = true; for (int i = 1; i <= A.length; i++) { for (int j = m; j >= 0; j--) { if (j - A[i - 1] >= 0 && DP[j - A[i - 1]]) { DP[j] = true; } } } for (int j = m; j >= 0; j--) { if (DP[j]) { return j; } } return 0; } } ``` |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |