Backpack
Description
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
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.
实现思路
我们可以建立一个(n+1)*(m+1)的状态数组dp[][],其中n=A.length, dp[i][j]为当背包总重量为j且有前i个物品时,背包最多装满dp[i][j]的空间。
状态转移方程为:dp[i][j] = Math.max(dp[i – 1][j – A[i]] + A[i], dp[i-1][j]);
dp[i – 1][j – A[i]] + A[i]为加入第i个物品后背包的总装满空间。
在进一步分析前,看看下面这个例子:
如果有4个物品[2, 3, 5, 7],如果背包的大小为11。问最多能装多满?
建动态规划数组 dp[A.length][m + 1],A.length行,m+1列
i \ j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
0(A[0]=2) | dp[0][0] = 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
1(A[1]=3) | 0 | 0 | 2 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
2(A[2]=5) | 0 | 0 | 2 | 3 | 3 | 5 | 5 | 7 | 8 | 8 | 10 | 10 |
3(A[3]=7) | 0 | 0 | 2 | 3 | 3 | 5 | 5 | 7 | 8 | 10 | 10 | 10 |
- 为了把第i个物品放进背包,背包当然要先腾出至少A[i]的空间,腾出后空间的最多装满空间为
dp[ i - 1][j - A[i]]
,再加上第i个物品的空间A[i],即为当背包总空间为j时,装入第i个物品背包的总装满空间。
比如当i=1,j=3,为了装上物品A[1],至少腾出A[1]=3的空间,腾出后空间的最多装满空间为:`dp[i-1][j-A[i]] = dp[0][0] = 0,再加上物品A[1],即为当背包总空间为j时,装入第i个物品背包的总装满空间dp[1][3] = 3. - 在1中的例子,dp[1][3]恰好存在3个单位空间可以把A[1]装上,但第i个物品所占的空间可能比此时背包的总空间j要大(j < A[i]),此时装不进第i个物品,因此此时背包的总装满空间为dp[i-1][j]。
比如表格中的前两列都为0,原因是第i(0,1,2,3)个物品的空间要求都比已有空间j(0,1)大,而当j=2是,i=0物品是能放进去的,但当i=1放不进去,所以取dp[i-1][j]=dp[0][2]=2
- 需要注意的是,有时候虽然第i个物品能够装入包中,但为了把第i个物品装入而拿出了其他物品,这个时候,我们需要权衡,是拿出物品装入新物品,还是保留原来物品,因为我们要得到最大的空间占有量,我们可以这样取:
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-A[i]] + A[i])
比如1中的例子,就是dp[0][2] = 2 < dp[0][0] + A[1] = 3,所以dp[1][3] = 3
结合以上过程,我们可以写出下面代码
/** * @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;
int dp[][] = new int[n+1][m+1];
for(int i = 0; i < n; i ++){
for(int j = 0; j <= m ; j ++){
//为了放入第i个物品,找到对于特定空间j的最优放置方案
if(A[i] > j){
//第i件大小大于当前背包大小
dp[i+1][j] = dp[i][j];
}else{
dp[i+1][j] = Math.max(dp[i][j],dp[i][j-A[i]] + A[i]);//是否为了放置新的而拿出旧的
}
}
}
return dp[n][m];
}
我们仔细观察,发现下一层的dp只和上一层有关,并且,并且对于每一层,后边的只和前面的有关,即dp[i][j] 只和dp[i-1][0…j]有关。
所以我们完全可以优化dp为一维数组,长度为m,计算时从后面往前算,即取j=m…1,通过dp[0..m-1]求新的dp[m]再通过dp[0…m-2]求新的dp[m-1]直到用dp[0]求dp[1],而dp[0]默认为0,来完成每一层的迭代更新,具体代码如下:
/** * @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
int n = A.length;
int dp[] = new int[m+1];
for(int i = 0; i < n; i ++){
for(int j = m; j >= A[i] ; j --){
dp[j] = Math.max(dp[j],dp[j-A[i]] + A[i]);
}
}
return dp[m];
}
今天的文章Backpack 解题报告 背包问题深入浅出分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/67170.html