LintCode 799 · Backpack VIII.java

Backpack with Value array:
note that: "Each item has different values and quantities."
function:
dp[i][j] |= dp[i - 1][j - A[i - 1] * k]; (when you take that ith item)
or
dp[i][j] = dp[i - 1][j]; (when you don't take that ith item)

	public class Solution {
	/**
	* @param n: the value from 1 - n
	* @param value: the value of coins
	* @param amount: the number of coins
	* @return: how many different value
	*/
	public int backPackVIII(int m, int[] A, int[] K) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	boolean[][] dp = new boolean[n+1][m+1];
	dp[0][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = false;
	}
	// dp: functions
	int counter = 0;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = true;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	for (int k = 1; k <= K[i - 1] && j - A[i - 1] * k >= 0; k++) {
	dp[i][j] |= dp[i - 1][j - A[i - 1] * k];
	}
	if (i == n && dp[i][j]) {
	counter++;
	}
	}
	}
	// for (int i = 0; i <= n; i++) {
	// System.out.println("Arrays.toString(dp[i]) = " + Arrays.toString(dp[i]));
	// }
	// dp: answer
	return counter;
	}
	}

view raw 799 · Backpack VIII.java hosted with ❤ by GitHub