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 II.java at master · awangdev/leet-code Expand file tree/ Copy pathBackpack II.javaMore file actions executable file ·322 lines (263 loc) · 9.08 KB / Copy pathBackpack II.javaFile metadata and controlsexecutable file ·322 lines (263 loc) · 9.08 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 317 318 319 320 321 322 M 1524202756 tags: DP, Backpack DP 给i本书, 每本书有自己的重量 int[] A, 每本书有value int[] V 背包有自己的大小M, 看最多能放多少value的书? #### Backpack DP - 做了Backpack I, 这个就如出一辙, 只不过: dp存的不是max weight, 而是 value的最大值. - 想法还是，选了A[i - 1] 或者没选A[i - 1]时候不同的value值. - 时间空间O(mn) - Rolling Array, 空间O(m) #### Previous DP Solution - 如果无法达到的w, 应该mark as impossible. 一种简单做法是mark as -1 in dp. - 如果有负数value, 就不能这样, 而是要开一个can[i][w]数组, 也就是backpack I 的原型. - 这样做似乎要多一些代码, 好像并不是非常需要 ``` /* Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack? Example Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9. Note You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m. Challenge O(n x m) memory is acceptable, can you do it in O(m) memory? Tags Expand LintCode Copyright Dynamic Programming Backpack */ /** Thoughts: dp[i][j]: 前i item, 放进weight/size = j 的袋子里的最大value. constraint: weight result: aggregate item value */ public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length != V.length) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i][j] = dp[i - 1][j]; if (j - A[i - 1] >= 0) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]); } } } return dp[n][m]; } } // Rolling array: public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length != V.length) { return 0; } int n = A.length; int[][] dp = new int[2][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i % 2][j] = dp[(i - 1) % 2][j]; if (j - A[i - 1] >= 0) { dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + V[i - 1]); } } } return dp[n % 2][m]; } } /* Thoughts: Dealing with value, the dp[i][w] = max value that can be formed over i tems at weight w. Two conditions: 1. didn't pick A[i - 1]: dp[i - 1][w], value sum does not change. 2. Picked A[i - 1]: dp[i - 1][w - A[i - 1]] + V[i - 1]; Find the max of the above two, and record. Initialize with dp[0][0] = -1: not possible to form w, so mark as -1, impossible. */ public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length != V.length) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; // [5][5] for (int j = 0; j <= m; j++) { dp[0][j] = -1; // 0 items cannot form weight j, hence value -1, marking impossible } dp[0][0] = 0; // 0 items, 0 weight -> 0 value for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j]; // 0 if (j - A[i - 1] >= 0 && dp[i - 1][j - A[i - 1]] != -1) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]); } } } int rst = 0; for (int j = 0; j <= m; j++) { if (dp[n][j] != -1) { rst = Math.max(rst, dp[n][j]); } } return rst; } } // Rolling array public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length != V.length) { return 0; } int n = A.length; int[][] dp = new int[2][m + 1]; for (int j = 0; j <= m; j++) { dp[0][j] = -1; // 0 items cannot form weight j, hence value -1, mark as impossible } dp[0][0] = 0; // 0 items, 0 weight -> 0 value int curr = 0, prev; for (int i = 1; i <= n; i++) { // rolling index prev = curr; curr = 1 - prev; for (int j = 1; j <= m; j++) { dp[curr][j] = dp[prev][j]; // 0 if (j - A[i - 1] >= 0 && dp[prev][j - A[i - 1]] != -1) { dp[curr][j] = Math.max(dp[curr][j], dp[prev][j - A[i - 1]] + V[i - 1]); } } } int rst = 0; for (int j = 0; j <= m; j++) { if (dp[curr][j] != -1) { rst = Math.max(rst, dp[curr][j]); } } return rst; } } /* Initialize with dp[0][0] = 0. This will pass the test, however it's not 100% explicit */ public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length != V.length) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; // [5][5] dp[0][0] = 0; // 0 items, 0 weight -> 0 value for (int j = 0; j <= m; j++) { dp[0][j] = 0; // 0 items cannot form weight j, hence value 0 } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j]; // 0 if (j - A[i - 1] >= 0) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]); } } } return dp[n][m]; } } // Rolling array public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length != V.length) { return 0; } int n = A.length; int[][] dp = new int[2][m + 1]; // [5][5] dp[0][0] = 0; // 0 items, 0 weight -> 0 value for (int j = 0; j <= m; j++) { dp[0][j] = 0; // 0 items cannot form weight j, hence value 0 } int curr = 0, prev; for (int i = 1; i <= n; i++) { // rolling index prev = curr; curr = 1 - prev; for (int j = 1; j <= m; j++) { dp[curr][j] = dp[prev][j]; // 0 if (j - A[i - 1] >= 0) { dp[curr][j] = Math.max(dp[curr][j], dp[prev][j - A[i - 1]] + V[i - 1]); } } } return dp[curr][m]; } } /* Previous Notes. Thoughts: In Backpack I, we store true/false to indicate the largest j in last dp row. Here, we can store dp[i][j] == max value. State: dp[i][j] : with i-1 items that fills exaclty size j, what's the max value Fn: still, picked or did not picked A[i-1] 1. Didn't pick. Value remains the same as if we didn't add A[i-1] 2. Picked A[i - 1]. Hence, find out previous record dp[i-1][j - A[i - 1]], then add up the A[i-1] item's value V[i-1]. 3. Compare 1, and 2 for max value. dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]) Init: dp[0][0] = 0; // 0 item, fills size 0, and of course value -> 0 Return: dp[A.length][m] Note: when creating dp, we do (A.length + 1) for row size, simply because we get used to checking A[i-1] for prevous record ... Just keep this style. Don't get confused. */ public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A & V: Given n items with size A[i] and value V[i] * @return: The maximum value */ public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length == 0 || V.length == 0 || A.length != V.length || m <= 0) { return 0; } int[][] dp = new int[A.length + 1][m + 1]; dp[0][0] = 0; // 0 item, to make pack size = 0, of course value = 0. for (int i = 1; i <= A.length; i++) { for (int j = 0; j <= m; j++) { if (j - A[i - 1] >= 0) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[A.length][m]; } } /* To use just O(m) sapce. Just like in Backpack I, at the end, we only care about the last row. Why not just maintain a row, always keep the max value. Note: Only update dp[j] if adding A[i-1] would be greater than current dp[j] It's a bit hard to come up with this... but it's good exercise. */ public class Solution { public int backPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length == 0 || V.length == 0 || A.length != V.length || m <= 0) { return 0; } int[]dp = new int[m + 1]; dp[0] = 0; // 0 item, to make pack size = 0, of course value = 0. 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]] + V[i - 1] > dp[j]) { dp[j] = dp[j - A[i - 1]] + V[i - 1]; } } } return dp[m]; } } ``` |
| 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. |