https://segmentfault.com/a/1190000006325321

Summary

• 总的来说就是2-d matrix, 纵坐标items volumes，横坐标backpack volumes from 0 to max

j ---->
i  0 1 2 3 4
|1
|2
v4

• 不能重复取 j 从最大扫到最小
• 可以重复取 j 从最小扫到最大
• backpack 六比较特殊 inner loop 是扫纵坐标 从上到下

Backpack I

Problem 单次选择+最大体积

dp[i][j] is the max volume that can put in the backpack if I have i items and the max volume is j

if A[i] is smaller than j, dp[i][j] = Math.max(dp[i - 1][j - A[i]] + A[i], dp[i - 1][j]);
else  dp[i][j] = dp[i - 1][j];

but I can reduce the use of extra space, since I only care the state of last row.

dp[j] = Math.max(dp[j], dp[j - A[i]]);

Mistakes

item i may not be chosen even if j is larger than it !!!!

thinking of this case

• [2,3,5,7], m=12

How to avoid using one item repeatedly?

• iterate over m from end to start

public int backPack(int m, int[] A) {
        // write your code here
        if (A == null || A.length == 0) return 0;

        int[] dp = new int[m + 1];

        for (int i = 0; i < A.length; ++i) {
            for (int j = m; j >= 0; --j) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
                }
            }
        }

        return dp[m];
    }

Backpack II

Problem 单次选择+最大价值

compare the value instead of the volume, so just change to V[i] instead of A[i]

public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[] dp = new int[m+1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
                }
            }
        }

        return dp[m];
    }

Backpack III

Problem 重复选择+最大价值

Since items can be selected more than once, then changing the j loop from start to end.

public int backPackIII(int[] A, int[] V, int m) {
        // Write your code here
        int[] dp = new int[m+1];
        for (int i = 0; i < A.length; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
                }
            }
        }

        return dp[m];
    }

Backpack IV

Problem 重复选择+唯一排列+装满可能性总数

dp[j] = the number of possible fill j using i items

public int backPackIV(int[] nums, int target) {
        // Write your code here
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = 1; j <= target; ++j) {
                if (nums[i] == j) {
                    dp[j]++;
                } else if (nums[i] < j) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }

        return dp[target];
    }

Backpack V

Problem 单次选择+装满可能性总数

public int backPackV(int[] nums, int target) {
        // Write your code here

        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j > 0; j--) {
                if (nums[i] == j) dp[j]++;
                else if (nums[i] < j) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }

Backpack VI

Problem 重复选择+不同排列+装满可能性总数

Loop through all the items before getting into the next backpack value.

because I wanna find out how many possibilities to fill current volume with all items and then the next I can add on to it

Thinking of this example: nums = [1,2,3], target = 4

  0 1 2 3 4
1 1 1 1 2 5
2 1 1 2 3 6
3 1 1 2 4 7

when j = 2
there are two possible after looping through all items [1, 1] [2]

then, next around when j = 3
for the first item, it could add on all possible combinations above [1, 1, 1] [2, 1]
for the second item, since the value is also smaller to j, it could be but j - nums[i] = 1, then [1, 2]
for the third item, [0, 3]

public int backPackVI(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num: nums) {
                if (num <= i) dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }