Backpack

题目

92. Backpack
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.

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.

Notice
You can not divide any item into small pieces.

答案

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 n = A.length;
        if(n == 0) return 0;
        int max_size = 0;
        boolean[][] f = new boolean[n + 1][m + 1];
        
        // Base cases
        f[0][0] = true;
        for(int i = 1; i <= m; i++) f[0][i] = false;
        
        // Fill dp array
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if(j >= A[i - 1])
                    f[i][j] = f[i][j] || f[i - 1][j - A[i - 1]];
                if(f[i][j])
                    max_size = Math.max(max_size, j);
            }
        }
        
        return max_size;
    }
}

空间优化

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 n = A.length;
        if(n == 0) return 0;
        int max_size = 0;
        boolean[][] f = new boolean[2][m + 1];
        
        // Base cases
        f[0][0] = true;
        for(int i = 1; i <= m; i++) f[0][i] = false;
        
        int old = 0, now = 0;
        // Fill dp array
        for(int i = 1; i <= n; i++) {
            old = now;
            now = 1 - old;
            for(int j = 0; j <= m; j++) {
                f[now][j] = f[old][j];
                if(j >= A[i - 1])
                    f[now][j] = f[now][j] || f[old][j - A[i - 1]];
                if(f[now][j])
                    max_size = Math.max(max_size, j);
            }
        }
        
        return max_size;
    }
}