背包问题——完全背包
本文最后更新于489 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com

完全背包实际上与01背包没什么区别,我们知道01背包的问题是这么描述的:

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

而这跟完全背包不同的地方在于完全背包的每种物品有无限个,01背包每种物品只有一个。

分析

那我们在考虑第i个物品时,除了要考虑该物品取不取,还要考虑该物品取多少个;

我们可以在01背包的基础上,再枚举该物品要取多少个;

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
        for(int k=0;k*v[i]<=j;k++)//对物品的数量进行枚举
        {
             dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);
        }
    }
}

你可能发现了,为什么是dp[i][j]而不是像01背包一样是dp[i-1][j]?

其实真正的状态转移方程是这样的:

max(dp[i-1][j],dp[i-1][j-v[i]*k]+w[i]*k)

当k=0时,dp[i][j]=max(dp[i-1][j],dp[i-1][j]),实际上是一样的,所以dp[i-1][j-v[i]*k]+w[i]*k就已经包括了

dp[i-1][j];又因为有这已成循环的存在,max里面的dp[i][j]也是必须要有的,此时的dp[i][j]记录的是k-1个i物品的总价值;

但如果这么写,时间复杂度大概为O(nm2),数据稍微强一点,肯定过不去;

优化

我们把方程展开之后发现:

dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*1]+w[i]*1,dp[i-1][j-v[i]*2]+w[i]*2,...,dp[i-1][j-v[i]*k]+w[i]*k);
dp[i][j-v[i]]=max(    dp[i-1][j-v[i]],         dp[i-1][j-v[i]*2]+w[i], ... ,dp[i-1][j-v[i]*k]+w[i]*(k-1));

比对之后我们可以发现:

dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);

我们就去掉了一层循环

for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
         dp[i][j]=dp[i-1][j];
         if(v[i]<=j)dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
    }
}

我们同样可以通过滚动数组将其变成一维的,最终代码就成了这样:

for(int i=1;i<=n;i++)
{
    for(int j=v[i];j<=m;j++)
    {
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    }
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇