今天学习了下背包问题，也就是传说中的NP问题，屌屌的。我学习的是最简单的背包问题。

打个简单的比方，假设你找到一片宝藏，这时候你有一个背包，这个背包是有容量限制的，最多只能装10公斤的东西。

然后宝藏中有各种宝石，黄金，和价值连城的珍珠，可惜的是，每件宝物都有其对应的价值和重量，这个时候问题就来了，你怎么选择，能够使得你背包里面装的宝物价值最大化呢？

假设现在宝藏中只有一个宝石，其价值是5，重量是3，那么你的选择是将宝石装进背包，这个时候，背包所承载的物品的价值是5，背包剩余的重量还剩7.

那么再假设下，现在宝藏中有两块宝石，宝石A价值是5，重量是3，宝石B的价值是6，重量是6. 那么你的选择当然是宝石A和宝石B一起放进去。那么这个时候，包包所承载的宝石价值就是11，重量是9. 那么假设宝石B的价值是6，但重量是8，那么就不能把A和B都放在背包了，因为两者重量加起来超过了10.所以要求价值最大化，就只能放宝石B。

还可以依次往下看三块宝石，四块宝石，五块宝石。。。的选择情况。

其实我这里没有讲的特别学院派，讲状态和状态转移方程。但是我的理解就是这样的。于是我照着这个思路，以及网上的源码，边理解边写了一遍，然后又用go去实现了这个算法。

这个问题可以用DP来解，也可以用MIP来解。不过对于我来说，用DP来解就已经很受用了，MIP太高端，我也摸不太透。

下面就解释下我的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def pack_result():
    """背包最大容量是10  总共4件物品，价值和重量分别如下
        Knapsack Max weight : W = 10 
        Total items         : N = 4
        Values of items     : v= [10, 40, 30, 50]
        Weight of items     : w = [5, 4, 6, 3]
        return：拿到最大价值，和背包的剩余容量
    """
    V = [10,40,30,50]  # 每个物品对应的价值
    W = [5,2,8,7] #每个物品的重量
    MAX = 9 #背包的最大载重量
    print getValue(W,V,MAX,4) #i=4,就代表有4件物品
def getValue(W,V,MAX,i):  #定义一个函数
    if i>1: 
        #不放第i件物品最大价值
        DoNotPutThe_indexi_goods_in_bag_Value,\
        DoNotPutThe_indexi_goods_in_bag_Weight = getValue(W,V,MAX,i-1)
        #如果第i件物品的重量大于背包最大容量
        if W[i-1] > MAX: # 如果这个地方为真，那就不能放i进去了，因为放i进去，背包就装不下了，既然不放i，那就是返回上面不放i的值，
            return DoNotPutThe_indexi_goods_in_bag_Value,DoNotPutThe_indexi_goods_in_bag_Weight
        else: #如果第i件物品的重量小于背包最大容量，那就可以把i放进去了。那把i放进去了后，包包剩下的重量就是max减去i的重量，
            changed_Value,changed_Weight = getValue(W,V,MAX-W[i-1],i-1)
            if changed_Value + V[i-1] > DoNotPutThe_indexi_goods_in_bag_Value:
                return changed_Value + V[i-1],changed_Weight
            else:
                return DoNotPutThe_indexi_goods_in_bag_Value,DoNotPutThe_indexi_goods_in_bag_Weight
     #可以先看else下面的，比较容易懂，意思就是如果只有一件物品，并且大于背包的重量，那么背包所承载的价值就为0，背包剩余容量就是没装东西的容量MAX
    else:
        if W[0] > MAX:
            return 0,MAX
# 如果这件物品小于背包的最大容量，那么就装进背包，那么背包所承载的价值就是这件物品的价值，背包剩余容量就是最大容量减去这件物品的重量
        else:
            return V[0],MAX - W[0]
if __name__ == '__main__':
    pack_result()

理解了原理，然后我有用Go实现了一版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package main
import (
	"fmt"
)
func getValue(W []int, V []int, MAX int, i int) (int, int) {
	var notiV, notW int  #一开始这两个变量没在这里定义，导致下面再次使用的时候报错说未定义
	if i > 1 {
		if W[i-1] > MAX {
			notiV, notW = getValue(W, V, MAX, i-1)
			return notiV, notW
		} else {
			puti_in_V, puti_in_W := getValue(W, V, MAX-W[i-1], i-1)
			if (puti_in_V + V[i-1]) > notiV {
				return (puti_in_V + V[i-1]), puti_in_W
			} else {
				return notiV, notW
			}
		}
	} else {
		if W[0] > MAX {
			return 0, MAX
		} else {
			return V[0], MAX - W[0]
		}
	}
}
func main() {
	V := []int{10, 20, 30, 40}
	W := []int{5, 4, 6, 2}
	MAX := 9
	fmt.Println(getValue(W, V, MAX, 4))
}

感觉屌屌哒，背包问题至少我知道了个大概。