动态规划
背包问题
问题：
假设你要去野营。你有一个容量为6磅的背包，需要决定该携带下面的哪些东西。其中每样东西都有相应的价值，价值越大意味着越重要：
- 水（重3磅，价值10）；
- 书（重1磅，价值3）；
- 食物（重2磅，价值9）；
- 夹克（重2磅，价值5）；
- 相机（重1磅， 价值6）。
请问携带哪些东西时价值最高？
画网格每一个网格代表一磅
cell[i][j] = max{1. 上一个单元格的值(即cell[i-1][j]的值) vs 2.当前商品的价值 + 剩余空间的价值(cell[i-1][j-当前商品的重量])}
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 水（w） | 10 w | 10 w | 10 w | 10 w | ||
| 书（b） | 3 b | 3 b | 10 w | 13 w,b | 13 w,b | 13 w,b |
| 食物（f） | 3 b | 9 f | 12 b,f | 13 w,b | 19 w,f | 22 w,b,f |
| 夹克(j) | 3 b | 9 f | 12 b,f | 14 f,j | 19 w,f | 22 w,b,f |
| 相机(c) | 6 c | 9 f | 15 f,c | 18 b,f,c | 20 f,c | 25 w,f,c |
代码
#动态规划
import numpy as np
#定义重量
weight = {}
weight["water"] = 3
weight["book"] = 1
weight["food"] = 2
weight["jacket"] = 2
weight["camera"] = 1
#定义价值
worth={}
worth["water"] = 10
worth["book"] = 3
worth["food"] = 9
worth["jacket"] = 5
worth["camera"] = 6
#存放行标对应的物品名
table_name={}
table_name[0] = "water"
table_name[1] = "book"
table_name[2] = "food"
table_name[3] = "jacket"
table_name[4] = "camera"
#创建矩阵，用来保存价值表
table = np.zeros((len(weight),6))
#创建矩阵，用来保存每个单元格中的价值是如何得到的（物品名）
table_class = np.zeros((len(weight),6), dtype=np.dtype((np.str_,500)))
for i in range(0,len(weight)):
for j in range(0,6):
#获取重量
this_weight = weight[table_name[i]]
#获得价值
this_worth = worth[table_name[i]]
#获取上一个单元格(i-1,j)的值
if(i>0):
before_worth = table[i-1,j]
#获取(i-1,j-当前商品的重量)
temp = 0
if(this_weight<=j):
temp = table[i-1,j-this_weight]
#(i-1,j - this_weight)+当前商品的价值
#判断this_worth能不能用，即重量有没有超标，如果重量超标了是不能加的
synthesize_worth = 0
if(this_weight-1<=j):
synthesize_worth = this_worth + temp
#与上一个单元格比较，哪个大写入哪个
if(synthesize_worth>before_worth):
table[i,j] = synthesize_worth
if(temp==0):
table_class[i][j] = table_name[i]
else:
#他自己和(i-1,j - this_weight)
table_class[i][j] = table_name[i] + "," + table_class[i-1][j-this_weight]
else:
table[i,j] = before_worth
table_class[i][j] = table_class[i-1][j]
else:
#没有(i-1,j)那更没有(i-1,j-重量),就等于当前商品价值，或者重量不够，是0
if(this_weight-1<=j):
table[i,j] = this_worth
table_class[i][j] = table_name[i]
print(table)
print("---------------------------------------------")
print(table_class)
运行结果
[[ 0. 0. 10. 10. 10. 10.]
[ 3. 3. 10. 13. 13. 13.]
[ 3. 9. 12. 13. 19. 22.]
[ 3. 9. 12. 14. 19. 22.]
[ 6. 9. 15. 18. 20. 25.]]
---------------------------------------------
[['' '' 'water' 'water' 'water' 'water']
['book' 'book' 'water' 'book,water' 'book,water' 'book,water']
['book' 'food' 'food,book' 'book,water' 'food,water' 'food,book,water']
['book' 'food' 'food,book' 'jacket,food' 'food,water' 'food,book,water']
['camera' 'food' 'camera,food' 'camera,food,book' 'camera,jacket,food'
'camera,food,water']]
