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];

}

}

```