LintCode 92 · Backpack

Classic backpack:
function:
dp[i][j] = dp[i - 1][j];
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i-1]] (if it can fit that ith item, aka: j - A[i-1] >= 0)

	public class Solution {
	/**
	* @param m: An integer m denotes the size of a backpack
	* @param A: Given n items with size A[i]
	* @return: The maximum size
	*/
	public int backPack(int m, int[] A) {
	// 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 maximumJ = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	dp[i][0] = true;
	for (int j = 1; j <= m; j++) {
	if (j - A[i-1] >= 0 && dp[i - 1][j - A[i-1]]) {
	dp[i][j] = true;
	} else {
	dp[i][j] = dp[i - 1][j];
	}
	if (i == n && dp[i][j]) {
	maximumJ = j;
	}
	}
	}
	// dp: answer
	return maximumJ;
	}
	}

view raw LintCode92 · Backpack.java hosted with ❤ by GitHub