Backpack II

Java

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
		public int backPackII(int m, int[] A, int[] V) {
			int n = A.length;
			if (n == 0) {
				return 0;
			}
			int f[][] = new int[n + 1][m + 1];
			f[0][0] = 0;
			int i, j;
			for (j = 1; j <= m; j++) {
				f[0][j] = -1; //impossible 
			}
		
			for (i = 1; i <= n; i++) {
				for (j = 0; j <= m; j++) {
					f[i][j] = f[i - 1][j];
					if (j >= A[i - 1] && f[i - 1][j - A[i - 1]] != -1) {
						f[i][j] = Math.max(f[i][j], f[i - 1][j - A[i - 1]] + V[i - 1]);
					}
				}
			}
			int res = 0;
			for (j = 0; j <= m; ++j) {
				if (f[n][j] != -1) {
					res = Math.max(res, f[n][j]);
				}
			}
			return res;
		}
}