Description

Given _n _items with size Ai, an integer _m _denotes the size of a backpack. How full you can fill this backpack?

Notice:

You can not divide any item into small pieces.

Example:

If we have4items 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 is10. If thebackpack size is12. 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.

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.

1. Solution

dp[i][j]表示容量j的背包在前i件物品中能选取的最大值。
状态基于两种情况：

不要第i件物品，此时容量为dp[i-1][j]
当第i件物品体积小于j时，可以选取第i件物品，则此时容量为第i件物品的体积加上在前i-1件物品中选取最大容量为j-A[i-1]的最大体积，即A[i] + dp[i-1][j-A[i]]
两种情况的最大值即当前(i,j)的最优解

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int[][] dp = new int[A.length + 1][m + 1];
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (A[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
                }
            }
        }
        return pack[A.length][m];
    }
}

2. Optimized Solution:

因为选取到第i件物品的状态只与前i-1件物品的状态相关，因此可以简化到只用一维数组的状态更新方程来解决。

注意第二层遍历的遍历顺序：
从小到大正向遍历时，dp[j]首先记录了(i, j)时的状态，遍历到(j'=j+A[i], i)时又更新dp[j]的状态，相当于重复选取了A[i]。因此正向遍历适用于允许重复选取元素的情况。
与之相反，从大到小反向遍历事，体积小于j的情况都没有遍历到，既然A[i]<=j，那么第i个物品放入的情况就相应没有讨论过，因此适用于不允许重复的情况。

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // 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 (A[i] <= j) {
                    dp[j] = Math.max(dp[j], dp[j-A[i]] + A[i]);
                }
            }
        }
        return dp[m];
    }
}

Backpack I