01背包 和 完全背包 详解
01背包 和 完全背包 详解
1944864971 发表于2年前
01背包 和 完全背包 详解
  • 发表于 2年前
  • 阅读 16
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

二维的就不用记了 二维的容易理解

看看一的

给一个在线生成的01背包的过程网址 http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html(需FQ

一组测试数据
背包容量 c =10
物品数量 n=5
每个物品的价值 v[]=5 4 3 2 1
重量 w[]=1 2 3 4 5

看代码:
for(int i=1;i<=n;i++)
for(int j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i])

讲解:

首先遍历所有的物品
然后倒着查看当前容量下所能放置的最大价值(为什么倒着查看 稍后讲)
比如当前物品的重量是3 先看容量为10的状态下 容量为10肯定可以放下重量为3 的物品 但是还余剩7的空间 7的空间总不能空这不用吧
这时我就找容量为7的状态下所能放置的最大价值(注意: 此时7的最大价值是在放置上一个物品之后所计算呢的最大价值 如果正序查看容量的话,就会先查看容量为7的状态下 那么就会把他的值更新了(此时已经把重量为3的物品装进去了 当查看容量为10 的时候他会先把3放进去 然后放7的最大值 可是7的最大值已经把3放进去了相当于放进去两次重量为3 的物品了 同理 查看容量为7 的时候 容量为4 的时候就已经把3放进去了 这样一来 等查看完容量为10的时候已经把重量为3 的物品放进去了3次 ~~哈哈哈这就是完全背包啊))

豁然开朗,,,,

很容易写出完全背包
or(int i=1;i<=n;i++)
for(int j=w[i];j<=c;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i])

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: