Backpack.md

##Backpack

19% Accepted

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

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.

####Note You can not divide any item into small pieces.

####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.

####Tags Expand

• LintCode Copyright
• Dynamic Programming
• Backpack

####基本做法

• Space O(m*n) 因为每次就在用f[i] f[i-1] 所以应该空间是可以优化的
• Time O(m*n)
• 参考 背包九讲
• f[i][j] = Math.max(f[i-1][j-A[i-1]] + V[i-1], f[i-1][j])

public class Solution {

    public int backPack(int m, int[] A) {
        // write your code here
        if (m ==0 || A == null || A.length == 0) {
            return 0;
        }
        int[][] f = new int[A.length+1][m+1];
        for (int i = 0; i <= m; i++) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= A.length; i++) {
            for (int j = 0; j <= m; j++) {
                if (j >= A[i-1]) {
                    f[i][j] = Math.max(f[i-1][j-A[i-1]] + A[i-1], f[i-1][j]);
                } else {
                    f[i][j] = f[i-1][j];
                }
            }
        }
        return f[A.length][m];
    }
}

####空间优化做法

• 优化f[i][j]到f[j]
• 此时第二重循环不能从j=0开始了，要从j=m开始 j--
• 如果是j=0 j++开始，那么f[j-A[i-1]]用的就是新的值，不是原来的f[i-1][j-A[i-1]]而是刚计算完的f[1] f[2]这样

public class Solution {

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

####或者这样更好理解

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
        if (m <= 0 || A == null) {
            return 0;
        }

        int n = A.length;
        int[][] result = new int[2][m+1];
        for (int i = 0; i <= m; i++) {
            result[0][i] = 0;
        }
        for (int i = 0; i <= 1; i++) {
            result[i][0] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 0; j--) {
                if (j - A[i-1] >= 0) {
                    result[i%2][j] = Math.max(result[(i-1)%2][j], result[(i-1)%2][j-A[i-1]] + A[i-1]);
                } else {
                    result[i%2][j] = result[(i-1)%2][j];
                }
            }
        }

        return result[A.length%2][m];
    }
}