内容简介:昨天阅读了程序员小灰的有n件物品和容量为cap的背包,每件物品有自己的容量w和价值v,每件物品只能选择放或者不放,求解让装入背包的物品容量不超过背包容量(cap)的情况下,能获得的最大价值是多少。小灰文章里举例的是工人挖矿,我们还是转换成物品放入背包的问题来描述,并且价值缩小10倍,只为了减少图片里表格的宽度。
前言
昨天阅读了 程序员 小灰的 《什么是动态规划》 ,当时还在亲戚家中,借了纸笔计算了一通,回家结合一些背包问题文章用程序实现了一下。文章先从简单的解决斐波那契数列入手,接着在讲解工人挖矿获取最大价值的例子中(其实就是经典的0-1背包问题),有一些容易使你晕头转向的问题,本文当作算法复习,并且记录了解题思路。
0-1背包问题
有n件物品和容量为cap的背包,每件物品有自己的容量w和价值v,每件物品只能选择放或者不放,求解让装入背包的物品容量不超过背包容量(cap)的情况下,能获得的最大价值是多少。
问题描述
小灰文章里举例的是工人挖矿,我们还是转换成物品放入背包的问题来描述,并且价值缩小10倍,只为了减少图片里表格的宽度。
我们把工人挖矿问题套用到背包问题里。容量=工人数,物品=金矿,背包装下最大物品价值=金库装下最大采集金矿价值
现有5个物品
假如背包容量只有10,应该如何选择物品才能使背包里的价值最大化?由于数据样本较少,只有5个,所以我们仅凭肉眼瞄一眼,能知道放入物品1和物品2需要5+5=10个容量,不超过背包容量,并且能获得90的最大价值。但是如果有100个物品呢,那光用眼看会瞎的。还是靠代码吧。
简要概括:5个物品,选择放入总容量为10的背包里,价值最大化是多少?
解题思路
1、设定基础变量
先设一下要用到的变量,在后面的程序会用上
var w [5] int = [5] int{5, 5, 3, 4, 3} //物品占用容量数组 var v [5] int = [5] int{40, 50, 20, 30, 30} //物品价值数组 var cap int = 10 //背包容量10
2、边界:v[0]
边界自然是只有一个物品的时候,只能把这个物品放入背包,没得选,边界是v[0]=40
3、最优子结构:F(n,c)=Max(不放入,放入)
我们先反过来想,放最后一个物品5的时候只有2种情况,情况1:不放入(放不下);情况2:放入。设定不放入的时候当前总价值是f1,放入的时候总价值是f2,那计算最后一个物品5的时候,就是在这2中情况总选择总价值最大的情况。设定函数F(n)表示处理第n个物品,那依据上面的反向思考,得出F(n)=Max(不放入,放入)。
4、方程:F(n,c)=Max(F(n-1,c),F(n-1,c-w[n])+v[n])
想一想不放入的情况,如果不放入,是不是就是等于处理上一个物品的情况,这次是n,上一次就是n-1,背包容量是c,所以不放入是F(n-1,c)。那放入的情况呢,那上一次的背包容量 就不是c了,要减去当前这个物品的容量w[n],最后得出的上一次的总价值
再加上这次物品的价值v[n],那结果是F(n-1,c-w[n])+v[n]。
编码解题
得出方程后,怎么写代码来运算呢,比较容易想到的是用递归算法的方式。从最后一个物品开始,逐步递归到第一个物品。
递归算法
var w [5] int = [5] int{5, 5, 3, 4, 3} //重量数组 var v [5] int = [5] int{400, 500, 200, 300, 350} //价值数组 func main() { var cap int = 10 var n int = len(w) max := computer(n-1, cap) fmt.Println("【", cap, "容量的背包在", n, "个物品里选择能装下的最大价值是", max, "】") } //递归 func computer(nIndex int, cap int) int { //基准条件:如果索引无效或者容量不足,直接返回当前价值0 if nIndex < 0 || cap <= 0 { return 0 } //不放第n个物品所得价值 res := computer(nIndex-1, cap) //放第n个物品所得值(前提是要放的下) if w[nIndex] <= cap { var f1 int = res //计算放的下的方案值 v[n]是当前物品的价值,computer(n-1, cap-w[n])是计算前一个物品,在减去这个物品容量后的容量下的最大价值方案 var f2 int = v[nIndex] + computer(nIndex-1, cap-w[nIndex]) //取两种方案最大价值那个 maxRes := maxForInt(f1, f2) res = maxRes } else { //fmt.Println(i, "|nIndex=", nIndex, ",", w[nIndex], ">", cap, "放不下") } return res }
运行结果
【 10 容量的背包在 5 个物品里选择能装下的最大价值是 90 】
处理每一物品/金矿的时候都有2个最优子结构,递归的执行流程类似一个高度为N的二叉树,所以时间复杂度:O(2^N)。看看有什么可以优化的吗,能发现计算结果是有重复的,那我们用一个map把计算的结果存储下来,每次计算之前从map里获取已经计算出的结果,避免重复计算。我们称它为备忘录方法或者记忆方法。
备忘录方法(记忆方法)
var memo map[string]int = make(map[string]int) //备忘录算法存储使用 //备忘录 func computer2(nIndex int, cap int) int { //基准条件:如果索引无效或者容量不足,直接返回当前价值0 if nIndex < 0 || cap <= 0 { return 0 } //如果此子问题已经求解过,则直接返回上次求解的结果 var key string = strconv.Itoa(nIndex) + "_" + strconv.Itoa(cap) res, ok := memo[key] if ok && res != 0 { return res } //不放第n个物品所得价值 res = computer2(nIndex-1, cap) //放第n个物品所得值(前提是要放的下) if w[nIndex] <= cap { var f1 int = res //计算放的下的方案值 v[n]是当前物品的价值,computer(n-1, cap-w[n])是计算前一个物品,在减去这个物品容量后的容量下的最大价值方案 var f2 int = v[nIndex] + computer2(nIndex-1, cap-w[nIndex]) //取两种方案最大价值那个 maxRes := maxForInt(f1, f2) res = maxRes //计算的结果存入备忘录,便于下次直接使用 memo[key] = res fmt.Println("保存计算结果", key, "=", res) } else { //fmt.Println(i, "|nIndex=", nIndex, ",", w[nIndex], ">", cap, "容量不足") } return res }
运行结果
【 10 容量的背包在 5 个物品里选择能装下的最大价值是 90 】
动态规划
我们来画个表格试着找下规律
填上边界值,前面分析过,边界值就是背包放置第一件物品的时候。第一件物品价值40,需要5的容量,那只要背包容量大于等于5的情况下都只有这一件物品可以选择,所以从容量5到最大容量10,最大价值都是40。
我们从上到下,从左至右,先把填充好的表格给大家看下。
直接看可能有点云里雾里,我再加上每个格子的计算过程。
能发现一个规律,每个格子都是和自己上一行(n-1)的格子进行比较,如果背包容量不够放不下,那最大值就是F(n-1,c),如果放的下,那就在上一行找到可以背包容量为(c-w[n])的最大值,再加上当前物品的价值v[n]。
挑一个格子来进行说明,就好理解了。如上图,我们看绿格子(第4行,第9列)最大价值80是怎么得出的,是根据上一行的2个黄格子得出的,首先根据公式 F(n,c)=Max(不放入,放入)
,情况1不放入的f1=70(上一行同一列的最大值),如果放入的话,当前物品的价值是v[n]=30,放入物品之前有多少容量呢,9-w[n]=3,那在第二行找3容量的背包最大值是f2=50,所以,max(70,50+30),80较大,那这个格子填入80。每个格子都可以套用这个思路去理解,那整个表格的最后一行的最后一格就是整个题目的最大化价值90。
来看下动态规划代码,代码变量拆分的比较细,是为了更好理解每个步骤的作用:
//动态规划 func computer3(nIndex int, cap int) int { size := cap + 1//+1是因为把第一个索引0表示为0个容量,虽然没有实际意义,但是让从索引1开始的位置代表1容量,便于理解。 preRes := make([]int, size) //上一轮最大价值存储 res := make([]int, size) //这一轮最大价值存储 //填充边界格子,把第一个物品放入能容纳下的第一行格子中 for i := 0; i <= cap; i++ { if i < w[0] { preRes[i] = 0 } else { preRes[i] = v[0] } } fmt.Println(1, preRes) //填充其他格子,外层循环是物品数量,内层循环是容量 for i := 1; i <= nIndex; i++ { for j := 0; j <= cap; j++ { vCurrent := v[i] //当前物品价值 wCurrent := w[i] //当前物品容量 f1 := preRes[j] //上一个不装的最大值 //判断是否装的下 if j < wCurrent { res[j] = f1 //fmt.Println("----", j, "装不下", wCurrent, "取值=", f1) } else { capCurrent := j - wCurrent //装下后的剩余容量 vPre := preRes[capCurrent] //获取上一轮剩余容量能存的最大价值 f2 := vPre + vCurrent biger := maxForInt(f1, f2) //fmt.Println("----", j, ">=", wCurrent, "装的下", f1, "vs", f2, "(", vPre, "+", vCurrent, ")", "=", biger) res[j] = biger } } //用深拷贝,把res赋值给上一个数组preRes,如果用preRes=res,则是操作一个数组 copy(preRes, res) fmt.Println(i+1, res) } return res[cap] }
运行结果
1 [0 0 0 0 0 40 40 40 40 40 40] 2 [0 0 0 0 0 50 50 50 50 50 90] 3 [0 0 0 20 20 50 50 50 70 70 90] 4 [0 0 0 20 30 50 50 50 70 80 90] 5 [0 0 0 30 30 50 50 60 80 80 90] 【 10 容量的背包在 5 个物品里选择能装下的最大价值是 90 】
时间复杂度:O(N*C),空间复杂度:O(C)。
算法比较
如果cap=10,n=5,递归算法的计算次数是2^N=32,动态规划算法的计算次数是N*C=50,递归算法更少。
但如果cap=100,n=50,递归算法的计算次数是2^50=1.1259e+15,动态规划算法的计算次数是100*50=5000,递归算法需要计算1亿多次,量级相当可怕,动态规划算法只要5000次。
所以算法没有一定意义上的好坏,具体看使用场景。
总结
归纳下重点:
解题步骤
1、边界
2、最优子结构
3、状态转移方程
公式
F(n,c) = max(F(n-1,c), F(n-1,c-w[n-1])+v[n-1])
时间复杂度
递归算法
时间:O(2^N),空间:O(1)。计算次数随,物品n数量成指数增长,数量n一多效率就低下。
动态规划算法
时间:O(N*C),空间:O(C)
欢迎关注我们的微信公众号,每天学习 Go 知识
以上所述就是小编给大家介绍的《golang实现和讲解动态规划算法(背包问题)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数据结构和算法面试题系列—背包问题总结
- 前端与算法-动态规划之01背包问题浅析与实现
- 前端学习算法2: 背包问题 ,一步一步思考(动态规划入门)
- 动态规划之背包问题
- 背包加密
- 王者编程大赛之三 — 01背包
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
1024·人与机器共同进化
东西文库 / 译言·东西文库/电子工业出版社 / 2013-12-20 / 55元
《1024》:国内第一本专注于科技文化的mook。 本期创刊号将目光定焦在“人与机器”这个超热点领域。 如果把机器获得思维能力看作是一种进化, 那人类具备不朽之躯同样也是一种进化。 这是一个野心勃勃但又充满不确定性的未来。 在我们一厢情愿地猜测机器将在不远的将来赶超自己而惶惶不可终日时,人类其实还有一个机会——变得更像机器。这并非科幻小说,而是正在发生的现实。人类创造......一起来看看 《1024·人与机器共同进化》 这本书的介绍吧!