Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack? Notice You can not divide any item into small pieces. Have you met this question in a real interview? Yes Example If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5],
so that the max size we can fill this backpack is 10. If the backpack size is 12.
we can select [2, 3, 7] so that we can fulfill the backpack. You function should return the max size we can fill in the given backpack. Challenge O(n x m) time and O(m) memory. O(n x m) memory is also acceptable if you do not know how to optimize memory. Tags LintCode Copyright Backpack Dynamic Programming
public int backPack(int m, int[] A) {
// write your code here
boolean[][] f = new boolean[A.length + 1][m + 1];
//initialize
f[0][0] = true;
for (int i = 1; i <= m; i++) {
f[0][i] = false;
}
for (int i = 1; i <= A.length; i++) {
f[i][0] = true;
}
//function
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= A.length; j++) {
f[j][i] = f[j - 1][i];
if (i >= A[j - 1] && f[j - 1][i - A[j - 1]]) {
f[j][i] = true;
}
}
}
for (int i = m; i >= 0; i--) {
if (f[A.length][i]) {
return i;
}
}
return 0;
}
用 integer 来替代
public int backPack(int m, int[] A) {
// write your code here
int[][] f = new int[A.length + 1][m + 1];
//initialize
f[0][0] = 0;
for (int i = 1; i <= m; i++) {
f[0][i] = Integer.MIN_VALUE;
}
for (int i = 1; i <= A.length; i++) {
f[i][0] = 0;
}
int ans = 0;
//function
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= A.length; j++) {
f[j][i] = f[j - 1][i];
if (i >= A[j - 1] && f[j - 1][i - A[j - 1]] != Integer.MIN_VALUE) {
f[j][i] = Math.max(f[j][i], f[j - 1][i - A[j - 1]] + A[j - 1]);
ans = Math.max(ans, f[j][i]);
}
}
}
return ans;
}
原文：http://www.cnblogs.com/apanda009/p/7291984.html