01背包问题(完全背包,部分背包)golang实现

Tibbersshao · · 2393 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

很经典的动态规划问题,具体思路这里就不列出了,网上太多资料了。想要详细理解的话可以去看背包九讲
这里分别列出,01背包,完全背包,部分背包 golang实现。
01背包
给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。
应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

从左往右,从上往下填表(example: 5表示重量,12表示价值)


1.png
1.png

代码and注释
dp[i][j] = max(dp[i-1][j], nums[i][1]+dp[i-1][j-nums[i][0]]) 仔细想清楚这一行


backpack.png
backpack.png

完全背包
给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi,每个物品都有无限多件,现在往背包里面装东西,怎么装能使背包的内物品价值最大?
先看图:
这是一个一维数组,每一行表示每次遍历的结果


2.png
2.png

代码and注释,理解上面一个,这个也很好理解


backpack1.png
backpack1.png

部分背包
给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi,每个物品都有ki件,现在往背包里面装东西,怎么装能使背包的内物品价值最大?
一个比较简单但是效率不高的方法: 把物品i的ki件物品转化为k件不同的物品,直接就转化为01背包问题了。不过效率较低。
另一种思路:再申请一个数组来保存物品i的使用个数,从而控制物品i的数量,用完全背包的思路解决问题
代码and注释


backpack3.png
backpack3.png

遍历过程:dp表示每遍历一个物品时的最优价值,count表示重量为n时放入物品i的个数
dp[0 0 0 0 0 8 8 8 8 8 16 16 16 16 16 16]
count[0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2]
dp[0 0 0 0 3 8 8 8 8 11 16 16 16 16 19 19]
count[0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1]
dp[0 0 0 0 3 8 8 10 10 11 16 16 18 18 20 20]
count[0 0 0 0 0 0 0 1 1 0 0 0 1 1 2 2]
dp[0 0 3 3 6 8 9 11 11 14 16 17 19 19 22 22]
count[0 0 1 1 2 0 3 1 1 2 0 3 1 1 2 2]
dp[0 0 3 3 6 8 9 11 11 14 16 17 19 19 22 22]
count[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

总结:
基本上背包问题的解题思路最终都会转化为01背包问题,核心代码都是基于一个公式:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
代码还有很大优化空间。只是记录一下自己的学习过程。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:Tibbersshao

查看原文:01背包问题(完全背包,部分背包)golang实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2393 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传