Backpack II

Backpack II (0 - 1背包问题)

0-1 knapsack problem

单次选择 + 最大价值

Question

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?

Notice

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

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.

Challenge

O(n x m) memory is acceptable, can you do it in O(m) memory?

Tags

LintCode Copyright Dynamic Programming Backpack

Related Problems

Medium Backpack VI 30 % Medium Backpack V 39 % Medium Backpack IV 36 % Hard Backpack III 50 % Medium Backpack 23 %

Analysis

https://github.com/tianyicui/pack/blob/master/V2.pdf

最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。0 - 1

子问题定义状态：即 F[i, v] 表示前 i 件物品放入一个容量为 v 的背包可以获得 的最大价值

其状态转移方程便是： F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci ] + Wi}

DP四要素

• 状态 State

  • f[i][j] 表示前 i 个物品当中选一些物品组成容量为 j 的最大价值

• 方程 Function

  • f[i][j] = max(f[i-1][j], f[i-1][j-A[i-1]] + V[i-1]);

• 初始化 Initialization

  • f[0][0] = 0;

• 答案 Answer

  • f[n][s]

• 时间复杂度 O(n*s)

Solution

2D DP

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_2(int m, int[] A, int[] V) {
        // maximum value of using first i items under total size j
        int[][] dp = new int[A.length + 1][m + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= A[i - 1]) {
                    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];
    }
}

1D DP space Optimized

用一维数组优化

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */

    public int backPackII(int m, int[] A, int[] V) {
        // maximum value of using first i items under total size j
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j >= A[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
            }
        }
        return dp[m];
    }
}