Backpack I 92
Question
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.
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.
Solution
基础背包类问题,用DP解。两种方法本质都一样,只是表述不同。
第一种方法为dp[i][j]表示i容量的背包在j件物品中能取的最大值。分两种情况:一种情况为不要第j件物品,则最优情况为背包容量为i时前j-1件物品的最优值;第二种情况为要第j件物品,则最优情况为背包容量为i-第j件物品体积时前j-1件物品的最优值加上第j件物品的值,这种情况要求i-第j件物品体积 >= 0。取两种情况里面较大的作为dp[i][j]的值。
第二种方法dp[i][j]表示前i件物品能否填满容量为j的背包。分两种情况:一种情况为不要第i件物品,则dp[i][j]=dp[i-1][j];第二种情况为要第j件物品,则dp[i][j] = dp[i-1][j - A[j]],不过这种情况要求j - A[j]>0。取两种情况里面较大的作为dp[i][j]的值。
代码如下:
Solution 1:
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(m == 0 || A == null || A.length == 0){
return 0;
}
int n = A.length;
int[][] fillPack = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++){
fillPack[i][0] = 0;
}
for(int j = 0; j <= n; j++){
fillPack[0][j] = 0;
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(i - A[j - 1] >= 0){
//一种情况为不要第j件物品,则最优情况为背包容量为i时前j-1件物品的最优值;第二种情况为要第j件物品,则最优情况为背包容量为i-第j件物品体积时前j-1件物品的最优值加上第j件物品的值。
fillPack[i][j] = Math.max(fillPack[i][j - 1], fillPack[i - A[j - 1]][j - 1] + A[j - 1]);
}else{
fillPack[i][j] = fillPack[i][j - 1];
}
}
}
return fillPack[m][n];
}
}
Solution 2:
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) {
boolean f[][] = new boolean[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = false;
}
}
f[0][0] = true;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j <= m; j++) {
f[i + 1][j] = f[i][j];
if (j >= A[i] && f[i][j - A[i]]) {
f[i + 1][j] = true;
}
} // for j
} // for i
for (int i = m; i >= 0; i--) {
if (f[A.length][i]) {
return i;
}
}
return 0;
}
}