LintCode 801 · Backpack X.java

Backpack with Value array:
note that: "And the number of these merchandises can be considered as infinite."
function:
dp[i] |= dp[i - nums[j] * k]; (when you take that ith item)
or
dp[i] = false; (when you don't take that ith item)

	public class Solution {
	/**
	* @param n: the money you have
	* @return: the minimum money you have to give
	*/
	public int backPackX(int target) {
	// write your code here
	if (target == 0) {
	return 0;
	}
	boolean[] dp = new boolean[target + 1];
	// dp: init
	dp[0] = true;
	// dp: states + functions
	int maximum = Integer.MIN_VALUE;
	int[] nums = new int[]{150, 250, 350};
	for (int i = 1; i <= target; i++) {
	for (int j = 0; j <= 2; j++) {
	int k = 1;
	while (i >= nums[j] * k) {
	dp[i] |= dp[i - nums[j] * k];
	k++;
	}
	}
	if (dp[i]) {
	maximum = i;
	}
	}
	// dp: answer
	return target - maximum;
	}
	}

view raw 801 · Backpack X.java hosted with ❤ by GitHub