Backpack III

题目

440. Backpack III
     Given n kind of items with size Ai and value Vi( each item has an infinite number available) and a backpack with size m. What's the maximum value can you put into the backpack?

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

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

答案

public class Solution {
    /**
     * @param A: an integer array
     * @param V: an integer array
     * @param m: An integer
     * @return: an array
     */
    public int backPackIII(int[] A, int[] V, int m) {
        int n = A.length;
        int[][] f = new int[n + 1][m + 1];

        
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                for(int k = 0; k * A[i - 1] <= j; k++) {
                    int t = f[i - 1][j - k * A[i - 1]] + k * V[i - 1];
                    f[i][j] = Math.max(f[i][j], t);   
                }
            }
        }
        
        return f[n][m];
    }
}

时间空间优化

public class Solution {
    /**
     * @param A: an integer array
     * @param V: an integer array
     * @param m: An integer
     * @return: an array
     */
    public int backPackIII(int[] A, int[] V, int m) {
        int n = A.length;
        int[][] f = new int[n + 1][m + 1];

        
        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] >= 0)
                    f[i][j] = Math.max(f[i][j], f[i][j - A[i - 1]] + V[i - 1]);
            }
        }
        
        return f[n][m];
    }
}