AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 3. 完全背包问题--一维动态规划转移过程模拟    原题链接    简单

作者: 作者的头像   polaris ,  2019-08-19 22:00:45 ,  阅读 6918


38


11

先上代码,和01背包问题的解法有略微的改动,区别在于遍历体积 $j$ 时从逆序改为顺序,在上一题中有我关于01背包问题的理解。

Python3 代码

if __name__ == '__main__':
    n, m = map(int, input().split())
    dp = [0] * (m + 1)
    v, w = [0], [0]
    for i in range(1, n + 1):
        line = list(map(int, input().split()))
        v.append(line[0])
        w.append(line[1])
        for j in range(v[i], m + 1):
            dp[j] = max(dp[j], dp[j - v[i]] + w[i])
    print(dp[m])

上一篇代码中,解释过,逆序是为了保证更新当前状态时,用到的状态是上一轮的状态,保证每个物品只有一次或零次;
在这里,因为每个物品可以取任意多次,所以不再强求用上一轮的状态,即本轮放过的物品,在后面还可以再放;

不妨按照思路,模拟一遍过程。

首先dp数组初始化全为0:给定物品种类有4种,包最大体积为5,数据来源于题目的输入
v[1] = 1, w[1] = 2
v[2] = 2, w[2] = 4
v[3] = 3, w[3] = 4
v[4] = 4, w[4] = 5

i = 1 时: j从v[1]到5
dp[1] = max(dp[1],dp[0]+w[1]) = w[1] = 2 (用了一件物品1)
dp[2] = max(dp[2],dp[1]+w[1]) = w[1] + w[1] = 4(用了两件物品1)
dp[3] = max(dp[3],dp[2]+w[1]) = w[1] + w[1] + w[1] = 6(用了三件物品1)
dp[4] = max(dp[4],dp[3]+w[1]) = w[1] + w[1] + w[1] + w[1] = 8(用了四件物品1)
dp[5] = max(dp[3],dp[2]+w[1]) = w[1] + w[1] + w[1] + w[1] + w[1] = 10(用了五件物品)

i = 2 时:j从v[2]到5
dp[2] = max(dp[2],dp[0]+w[2]) = w[1] + w[1] = w[2] =  4(用了两件物品1或者一件物品2)
dp[3] = max(dp[3],dp[1]+w[2]) = 3 * w[1] = w[1] + w[2] =  6(用了三件物品1,或者一件物品1和一件物品2)
dp[4] = max(dp[4],dp[2]+w[2]) = 4 * w[1] = dp[2] + w[2] =  8(用了四件物品1或者,两件物品1和一件物品2或两件物品2)
dp[5] = max(dp[5],dp[3]+w[2]) = 5 * w[1] = dp[3] + w[2] =  10(用了五件物品1或者,三件物品1和一件物品2或一件物品1和两件物品2)

i = 3时:j从v[3]到5
dp[3] = max(dp[3],dp[0]+w[3]) = dp[3] = 6 # 保持第二轮的状态 
dp[4] = max(dp[4],dp[1]+w[3]) = dp[4] = 8 # 保持第二轮的状态 
dp[5] = max(dp[5],dp[2]+w[3]) = dp[4] = 10 # 保持第二轮的状态

i = 4时:j从v[4]到5
dp[4] = max(dp[4],dp[0]+w[4]) = dp[4] = 10 # 保持第三轮的状态
dp[5] = max(dp[5],dp[1]+w[4]) = dp[5] = 10 # 保持第三轮的状态

上面模拟了完全背包的全部过程,也可以看出,最后一轮的dp[m]即为最终的返回结果。

上述代码可以进行简化

根据模拟过程可以发现,遍历每一轮i时,用到的v[i]和w[i]只来自本轮的输入,并且之后不会再用到,因此不用创建数组来存这两个值。

if __name__ == '__main__':
    n, m = map(int, input().split())
    dp = [0] * (m + 1)
    for i in range(1, n + 1):
        v, w = map(int, input().split())
        for j in range(v, m + 1):
            dp[j] = max(dp[j], dp[j - v] + w)
    print(dp[m])

16 评论


用户头像
楚天   2个月前     回复

大神,如果背包的体积变成了1e9怎么做

用户头像
虹之间   2个月前     回复

如果物品价值和小于一个较小的数的话,可以换种思路,枚举价值为一个定值时需要的最小体积


用户头像
皮KA丘   3个月前     回复

滚动数组?


用户头像
谷骋宇   3个月前     回复

orz


用户头像
置顶抽风   5个月前     回复

非常好!


用户头像
鬼子进村   6个月前     回复

大佬,我想问下如果背包容量变为10的9次方该怎么做呢


用户头像
cht   7个月前     回复

Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz


用户头像
Jhon   8个月前     回复

强啊,大佬一目了然


用户头像
fedfan   8个月前     回复
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];//体积是i的背包能装下的最大价值


int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i]>> w[i];
    for(int i = 0;i <= m;i ++)
    {
       for(int j = 1; j <= n; j ++)
       {
           if(i < v[j]) continue;
           f[i] = max(f[i], f[i - v[j]] + w[j]);
       }
    }
    cout<<f[m]<<endl;
}

改变状态表示,直接从一维的角度理解完全背包

用户头像
fedfan   8个月前     回复

https://www.acwing.com/solution/acwing/content/12878/ 理解不了从二维角度优化空间成一维,可以改变状态表示成f[i]体积是i的背包能装下的最大价值,直接从一维的角度理解完全背包


用户头像
zacker   10个月前     回复

这两个过程好像写错了:
i=3时的 dp[5] = max(dp[5],dp[2]+w[3]) = dp[5] = 10
i = 4时的 dp[4] = max(dp[4],dp[0]+w[4]) = dp[4] = 8


用户头像
之歌   10个月前     回复

果然还是把过程列出来才更有助于理解,真是好奇大神们是不是仅需要抽象的言语表述就能理解这个过程了。。。。


用户头像
0610   10个月前     回复

666


用户头像
zhengenxi   11个月前     回复

太详细了!!!Orz


用户头像
Moon_light   2019-11-04 09:10     回复

赞👍!


用户头像
Ace   2019-11-03 09:29     回复

厉害(。^▽^)

你确定删除吗?

© 2018-2020 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息