Backpack III

Description

Given n kinds of items, and each kind of item has an infinite number available. The i-th item has size A[i] and value V[i].

Also given a backpack with size m. What is the maximum value you can put into the backpack?

1. You cannot divide item into small pieces.
2. Total size of items you put into backpack can not exceed m.

Example

Example 1:

Input: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
Output: 15
Explanation: Put three item 1 (A[1] = 3, V[1] = 5) into backpack.

Example 2:

Input: A = [1, 2, 3], V = [1, 2, 3], m = 5
Output: 5
Explanation: Strategy is not unique. For example, put five item 0 (A[0] = 1, V[0] = 1) into backpack.

 思路：跟backpackII类似：

跟背包I类似，f[i][j]表示前i种物品组成重量为j的pack的总value是多少；我们还是从A[i-1] 能否进入pack来考虑

f[i][j] = Max( f[i-1][j] (不进去）, (进去）f[i-1][j - k * A[i-1]] + k*V[i-1] ,前提条件是: j -A[i-1] >=0 && f[i-1][j- k * A[i-1]] != -1;

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[][] dp = new int[n + 1][m + 1];
        for(int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }

        int maxres = 0;
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j];
                    for(int k = 0; j - k * A[i - 1] >= 0; k++) {
                        if(dp[i - 1][j - k * A[i - 1]] != -1) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k* V[i - 1]);
                        }
                    }
                }
                maxres = Math.max(maxres, dp[i][j]);
            }
        }
        return maxres;
    }
}