Backpack

Java

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) {
			int n = A.length;
			if (n == 0) {
				return 0;
			}
			// 0个也算一种情况，所以是n+1种情况；0公斤也是一种情况，所以m+1种公斤的情况
			boolean[][] f = new boolean[n + 1][m + 1]; 
			int i, j;
			f[0][0] = true;
			for (i = 1; i <= m; ++i) {
				f[0][i] = false;
			}
			
			//first i items 
			for (i = 1; i <= n; ++i) {
				for (j = 0; j <= m; ++j) {
					if (j - A[i - 1] >= 0) {
						f[i][j] = f[i - 1][j] || f[i - 1][j - A[i - 1]];
					} else {
						f[i][j] = f[i - 1][j];
					}
				}
			}
			int res = 0;
			//find maximum j such that f[n][i] = True
			for (j = m; j >= 0; j--) {
				if (f[n][j]) {
					res = j;
					break;
				}
			}
			return res;
		}
}