Problem

Given n items with size Ai, an integer m denotes the size of a backpack. 
How full you can fill this backpack?

Example
If we have 4 items 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 is 10. If the backpack size is 12. 
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.

思路

• 通过背包体积来画搜索树, 像总结里那样. 然后解释为什么需要增加前i个物品作为维度
• state
  • dp[i][S] 代表前 i 个物品, 取出一些, 能否组成和为 S
• function
  • 画出矩阵, 判断第i个物品取还是不取
  • a[i-1] 是第i个物品下标是i-1
  • f[i][j] = f[i-1][j - a[i-1]] or f[i-1][j]
  • 关键要判断 j >= a[i - 1]
• initialize
  • f[i][0] = true;
  • f[0][1..target] = false
• answer
  • 检查所有的f[n][j]

    public int backPack(int m, int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        boolean[][] dp = new boolean[n + 1][m + 1];


        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= A[i - 1]) {
                    dp[i][j] |= dp[i - 1][j - A[i - 1]];
                }
            }
        }

        for (int i = m; i >= 0; i--) {
            if (dp[n][i]) {
                return i;
            }
        }
        return 0;
    }

滚动数组优化

    public int backPack(int m, int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int n = A.length;
        boolean[][] dp = new boolean[2][m + 1];


        for (int i = 0; i <= 1; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i%2][j] = dp[(i - 1)%2][j];
                if (j >= A[i - 1]) {
                    dp[i%2][j] |= dp[(i - 1)%2][j - A[i - 1]];
                }
            }
        }

        for (int i = m; i >= 0; i--) {
            if (dp[n%2][i]) {
                return i;
            }
        }
        return 0;
    }