Lintcode 440. Backpack III

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?

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.

Notice

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

Solution:
A backpack DP problem. Define dp[N+1][m+1] where dp[i][j] means for the first i kinds of items with capacity j, what's the max value can we get?

So the transit function is
dp[i][j] = max(dp[i - 1][j], dp[i][j - A[i - 1]] + V[i - 1]);
The first item means we don't choose the ith item. The second means since the ith item can be picked up multiple times, from the first i items, with capacity j - A[i - 1], if we want to choose again, the value should be dp[i][j - A[i - 1]] + V[i - 1]

Code (Java):

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) {
        if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
            return 0;
        }
        
        int[][] dp = new int[A.length + 1][m + 1];
        
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - A[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);
                }
            }
        }
        
        return dp[A.length][m];
    }
}