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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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];     } }