Backpack
Backpack (0 - 1 背包问题)
0-1 knapsack problem
单次选择 + 最大体积
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.
Tags
LintCode Copyright Dynamic Programming Backpack
Related Problems
Medium Backpack VI 30 % Medium Backpack V 38 % Medium Backpack IV 36 % Hard Backpack III 50 % Medium Backpack II 37 %
Analysis
背包问题序列I
要点: 单次选择+最大体积
常用是DP,但也可以用递归+记忆化搜索来做。
这个问题没有给每个物品的价值,也没有问最多能获得多少价值,而是问最多能装多满。
实际上在这里,如果我们把每个物品的大小当作每个物品的价值,就可以完美解决这个问题。
Solution
Preferred Solution
2D - DP
状态:
dp[i][j]
- 代表在前 i
件物品中选择若干件,这若干件物品的体积和不超过 j
的情况下,所能获得的最大容量
外层循环A[i]
, 内层循环j
状态转移:
if (j >= A[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
2D DP
public int backPack(int m, int[] A) {
int[][] dp = new int[A.length + 1][m + 1];
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
if (j >= A[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[A.length][m];
}
Or Another 2D DP
public int backPackI(int m, int[] A) {
int dp[][] = new int[A.length + 1][m + 1];
for(int i = 1; i < A.length + 1; i++){
for(int j = 0; j < m + 1; j++){
dp[i][j] = dp[i-1][j];
if(j >= A[i - 1]){
dp[i][j] = Math.max(dp[i][j], dp[i-1][j - A[i-1]] + A[i-1]);
}
}
}
return dp[A.length][m];
}
1D - DP
State: 数组dp[i]
表示书包空间为i
的时候能装的A物品最大容量
动规经典题目,用数组dp[i]
表示书包空间为i
的时候能装的A物品最大容量。
两次循环,外部遍历数组A,内部反向遍历数组dp,若j
即背包容量大于等于物品体积A[i]
,则取前i - 1
次循环求得的最大容量dp[j]
,和背包体积为j - A[i]
时的最大容量dp[j - A[i]]
与第i
个物品体积A[i]
之和即dp[j - A[i]] + A[i]
的较大值,作为本次循环后的最大容量dp[i]
。
注意dp[]
的空间要给m+1
,因为我们要求的是第m+1
个值dp[m]
,否则会抛出OutOfBoundException。
一维数组优化:
在第 i
层循环初 dp[j]
存的相当于 dp[i - 1][j]
的值,因为在更新dp[j]
时用到了 dp[j - A[i]]
, 由于内层循环倒序,所以dp[j - A[i]]
未被更新,因此代表了dp[i-1][j - A[i]]
。
1D space optimized:
public class Solution {
public int backPack(int m, int[] A) {
int[] dp = new int[m+1];
for (int i = 0; i < A.length; i++) {
for (int j = m; j > 0; j--) {
if (j >= A[i]) {
dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
}
}
}
return dp[m];
}
}
1D DP
j = m, m-1, ..., A[i]
public int backPack(int m, int[] A) {
int[] dp = new int[m + 1];
for (int i = 0; i < A.length; i++) {
for (int j = m; j >= A[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
}
}
return dp[m];
}
Another DP Approach (NOT Preferred)
2D with O(n * m) time and O(n * m) space.
动态规划4要素
State:
f[i][S]
“前i”个物品,取出一些能否组成和为S
Function:
f[i][S] = f[i-1][S - a[i]]
orf[i-1][S]
Initialize:
f[i][0] = true
;f[0][1..target] = false
Answer:
检查所有的
f[n][j]
O(n * S) , 滚动数组优化
注意这里A[i - 1]的数组下标,因为新建的是i = 1, ..., A.length
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[][] dp = new boolean[A.length + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= A.length; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j] || (j - A[i - 1] >= 0 && dp[i - 1][j - A[i - 1]]);
}
}
for (int j = m; j >= 0; j--) {
if (dp[A.length][j]) {
return j;
}
}
return 0;
}
}
1D version with O(n * m) time and O(m) memory.
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) {
if (A.length == 0) return 0;
int n = A.length;
boolean[] dp = new boolean[m + 1];
Arrays.fill(dp, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
if (j - A[i - 1] >= 0 && dp[j - A[i - 1]]) {
dp[j] = dp[j - A[i - 1]];
}
}
}
for (int i = m; i >= 0;i--) {
if (dp[i]) return i;
}
return 0;
}
}
Memoization + Search
https://www.jiuzhang.com/solution/backpack/#tag-other
int max = Integer.MAX_VALUE;
public int backPack(int m, int[] A) {
Arrays.sort(A);
boolean[] visited = new boolean[m + 1];
int[] memo = new int[m + 1];
dfs( m , A , 0 ,visited , memo );
return m - max ;
}
private int dfs( int target , int[] A , int startIndex , boolean[] visited , int[] memo){
if(visited[target]){
return memo[target];
}
int res = target;
for(int i = startIndex ; i < A.length ; i++){
if(target - A[i] >= 0){
res = dfs( target - A[i] , A , i + 1 ,visited ,memo);
}
else{
break;
}
}
visited[target] = true;
memo[target] = res;
max = Math.min(max ,res);
return res;
}
Reference
Last updated
Was this helpful?