Backpack 解题报告 背包问题深入浅出

Backpack 解题报告 背包问题深入浅出BackpackDescriptionGivennitemswithsizeAi,anintegermdenotesthesizeofabackpack.Howfullyoucanfillthisbackpack?E

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
  1. 为了把第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.
  2. 在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
  3. 需要注意的是,有时候虽然第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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注