golang实现动态规划算法(背包问题)

本文是学习完算法图解之后的总结以及代码实现，第一部分是问题引入，第二部分是动态规划工作原理简介，第三部分是基于golang的代码实现

问题引入

【以小偷到商店偷东西为例，假设小偷有个4磅容量的背包，商店里有吉他、音响、笔记本电脑三样商品，吉他一磅重，价值1500，音响4磅，价值3000，笔记本3磅价值2000，问怎么才能让此次偷盗价值最大化？】

对于这个问题，很容易想到偷吉他和笔记本电脑价值最高为3500，如果再增加几个商品呢？

我们先来看看只有三个商品的时候都有那些选择组合，如下图，组合里总容量大于4的不能装到背包里，在剩余的组合中选择最大价值的组合，所以是吉他和笔记本组合，组合数是 2^n ，当商品数量增加时组合数呈指数增长，当商品很多时显然这个方法不合适，

那如何找到最优解呢？就是我们接下来要介绍的动态规划

动态规划算法工作原理

动态规划的思想是先解决小问题，再逐步解决大问题，背包问题来说，就是先解决小背包的问题，再解决大背包的问题

每个动态规划都是从一个网格开始的，背包问题网格如下。

商品/ 背包容量	1	2	3	4
吉他
音响
笔记本

网格的每行表示当前可偷的商品，第一行只能偷吉他，第二行能偷吉他和音响，第三行笔记本音响吉他。。。如还有商品以此类推，列表示当前背包的容量，我们把原本4磅的背包拆分成1-4磅的小背包，接下来我们逐行处理来看看。

吉他行：第一行第一列，吉他重量1，第一列表示背包的容量也是1，刚刚好可以放下，那第一个单元格的最大价值就是1500，

第二列两磅，也可以放下吉他，故最大价值也是1500，第三列3磅自然可以放下，且慢！笔记本也是3磅啊，记住！第一行只有吉他可以偷，我们要记住动态规划的思路是先从小问题逐步解决大问题，这很重要，所以第三个单元格最大价值只能是1500，第四个单元格也一样

商品/ 背包容量	1	2	3	4
吉他	1500	1500	1500	1500
音响
笔记本

接下来我们看第二行，音响行，这时候你可以偷的商品是吉他和音响了，这时候我们开始考虑，第一列能放下一个四磅重的音响吗？答案是不能，我们知道这时候还有吉他可选，吉他是1磅的，故而这时最大价值只1500，那么第二、三列情况和第一列是一样的，来到第四列，这是一个四磅背包，那么音响能不能装进背包呢？刚刚好音响是4磅重的。那应不应该放进背包呢？当只有吉他的时候四磅重的背包最大价值是1500，音响的价值是3000，显然应该装进背包。

商品/ 背包容量	1	2	3	4
吉他	1500	1500	1500	1500
音响	1500	1500	1500	3000
笔记本

来到第三行，我们可选的商品有吉他、音响、笔记本，我们来看第1列，笔记本3磅，无法放入1磅的背包中，观察这个表格，笔记本无法放入，只有音响和吉他可选择的时候，1磅背包的最大价值是多少呢？我们只需要看上一行的可以了。第2列同第1列一样，第三列有不同了，其实对每个单元格，我们都在考虑几个问题，当前的背包能放的下吗？不能的话，当前能放进背包的最大价值是多少？能的话，我该不该放进背包呢？好的，我们就按这个思路来看下，当前3磅的背包能放下吗？答案是能？那我们应该放进去吗？如果我们不放笔记本，那当前的最大价值是1500，而笔记本价值2000，显然应该放进背包，这时更新了背包的最大价值2000，来看看最后一个单元格，4磅的背包能放的下笔记本，那我们该不该放进背包呢？，如果不放笔记本的话，当前的最大价值是3000，等等，放笔记本的话，不是还有1磅的空间吗？我们还有可选择的子背包，1磅的背包最大价值是1500啊，这样背包的最大价值是3500了。

商品/ 背包容量	1	2	3	4
吉他	1500	1500	1500	1500
音响	1500	1500	1500	3000
笔记本	1500	1500	2000	3500

回顾整个填充网格的过程。可提炼公式如下

cell[n][m]= max (上一个单元格的值[cell[n][m-1], 当前商品的价值+剩余空间的价值cell[n-1][m-当前商品的重量])

我们求解每个单元格的目的就是要合并两个子单元格来解决更大的问题。

代码实现

接下是用golang实现的动态规划算法。

package main

import "fmt"

const (
	// 行
	RAW int = 4
	// 列
	COL int = 5
)

// 物品的重量 舍弃数组的0位置元素
var weight = [RAW]int{0, 1, 4, 3}

// 物品的价值 舍弃数组的0位置元素
var value = [RAW]int{0, 1500, 3000, 2000}

// 动态规划网格
var cells [RAW][COL]int

// 用于回溯选择的商品 selected[i]=1 表示放进背包，0表示不放进背包
var selected [RAW]int

// 动态规划计算网格
func dynamic() {

	for i := 1; i < len(value); i++ {
		for j := 1; j < 5; j++ {
			cells[i][j] = maxValue(i, j)
		}
	}
	for i := 0; i < RAW; i++ {
		fmt.Printf("raw is %v \n", cells[i])
	}
	findBack()
	fmt.Printf("selected goods is %v \n", selected)
}

// 判断当前单元格最大价值方法
func maxValue(i, j int) int {
	// 当前商品无法放入背包，返回当前背包所能容纳的最大价值
	if j < weight[i] {
		return cells[i-1][j]
	}
	// 可放进背包时候，计算放入当前商品后的最大价值
	curr := value[i] + cells[i-1][j-weight[i]]
	// 与当前商品不放进背包的最大价值比较，看是否应该放进背包
	if curr >= cells[i-1][j] {
		return curr
	}
	return cells[i-1][j]
}

// 回溯选择的商品方法
func findBack() {
	col := COL - 1
	for i := RAW - 1; i > 0; i-- {
		if cells[i][col] > cells[i-1][col] {
			selected[i] = 1
			col = col - weight[i]
		} else {
			selected[i] = 0
		}
	}
}

运行结果如下：

raw is [0 0 0 0 0] 
raw is [0 1500 1500 1500 1500] 
raw is [0 1500 1500 1500 3000] 
raw is [0 1500 1500 2000 3500] 
selected goods is [0 1 0 1]

看到这里，你是否想到，如果我们继续增加商品，比如增加一个重一磅，价值1500的小烤箱会怎么样？我们来试试

在表格中新增烤箱列，来到第四行，这时候我们可选择的商品多了一个烤箱，第一个单元是可以放下烤箱的，

我们发现吉他和烤箱都是一磅，我们要不要放进背包呢？其实二选一即可，后面的列按之前的规则填满即可，最大价值仍然是3500，这时我们知道了可选择商品可以是吉他和笔记本，也可以是烤箱和笔记本，但是我们的算法只能给出最优解中的一个。

商品/ 背包容量	1	2	3	4
吉他	1500	1500	1500	1500
音响	1500	1500	1500	3000
笔记本	1500	1500	2000	3500
烤箱	1500	1500	2000	3500

********************************************************* 正文完 ********************************************************

本文是看完《算法图解》之后基于书上原理的代码实现，本来只想写代码实现算法，想了想把算法原理也整理了一遍，碍于能力有限，如文中有所欠缺，请阅读《算法图解》第九章。