LintCode 798 · Backpack VII.java

Backpack with Value array:
note that: "Given the weight, price and quantity constrains."
function:
dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]); (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 money of you
	* @param prices: the price of rice[i]
	* @param weight: the weight of rice[i]
	* @param amounts: the amount of rice[i]
	* @return: the maximum weight
	*/
	public int backPackVII(int m, int[] A, int[] V, int[] K) {
	// write your code here
	if (A == null || A.length == 0) {
	return 0;
	}
	int n = A.length;
	// init
	int[][] dp = new int[n+1][m+1];
	dp[0][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[0][j] = 0;
	}
	// dp: functions
	int maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = 0;
	for (int j = 1; j <= m; j++) {
	dp[i][j] = dp[i - 1][j];
	int k = 1;
	while (j - A[i-1] * k >= 0) {
	dp[i][j] = Math.max(dp[i - 1][j - A[i - 1] * k] + V[i - 1] * k, dp[i][j]);
	k++;
	if (K[i - 1] < k) {
	break;
	}
	}
	}
	}
	// dp: answer
	return dp[n][m];
	}
	}

view raw 798 · Backpack VII.java hosted with ❤ by GitHub