#背包问题
# i 物品序号(总共多少物体) w物品体积 v物品价值 g背包容量 V总价值
# 对于第i个物品，有拿和不拿两种行为，取价值最高的。
# max{V（i-1，g）, V(i-1,g-w)+vi}
# V（i-1，g）不拿当前物体，总价值就是拿上一个物体的价值。
# V(i-1,g-wi)+vi拿当前物体，总价值就是拿上一个物体的价值加上当前i的价值。g-w的意思是背包要给当前物体留下足够的空间。
import numpy
FIND=[]
def bag (i:int, w:list, v:list, g:int):
table=[[0 for i in range(g+1)] for i in range(i+1)]
# print('初始化列表', '\n', numpy.mat(table))
for ii in range(i+1)[1:]:
for gi in range(g+1)[1:]:
if w[ii-1] > gi:
table[ii][gi] = table[ii-1][gi]
# print('超重table{}{}'.format(ii, gi), '\n',numpy.mat(table))
else:
table[ii][gi] = max(table[ii-1][gi], (table[ii-1][gi-w[ii-1]])+v[ii-1])
# print('没有超重table{}{}'.format(ii, gi), '\n', numpy.mat(table))
# print(numpy.mat(table))
return table
def bag2(k: int, w: list, v: list, W: int):
'''
:param k:最大数量减1
:param w: 重量
:param v: 价值
:param W: 背包容量
:return:递归的方式返回能装进包里的最大价值
'''
if k == -1:
return 0
if w[k] > W:
return bag2(k-1, w, v, W)
else:
return max(bag2(k-1, w, v, W), bag2(k-1, w, v, W-w[k])+v[k])
# yield
def find_what(row:int, line:int, table:list, w: list):
'''
:param row: 装最多的行数
:param line: 装最多的列数
:param table: 规划表
:param w: 物品体积表
:return:递归的方式寻找最优解
'''
if row >=0:
if table[row][line] == table[row-1][line]:
return find_what(row - 1, line, table, w)
else:
FIND.append(w[row-1])
return find_what(row - 1, line - w[row-1], table, w)
if __name__ == '__main__':
tab=bag(5, [5, 8, 13, 27, 14], [5, 8, 13, 27, 14], 33)
s= find_what(5, 32, tab, [5, 8, 13, 27, 14])
print(FIND)
