动态规划--01背包问题

解题思路

二维列表思路def bag_value(ls, vol):""":param ls: 水果体积及价值列表，列表长度表示水果种类，ls[i][0]表示体积，ls[i][1]表示价值，:param vol:背包体积ls = [[3, 1], [4, 5], [5, 6], [7, 9]]vol = 10:return:"""num = len(ls)   # 物品种类# 生成一个二维列表存放当前背包体积时的最优价值dp_ls = [[0 for _ in range(vol+1)] for _ in range(len(ls)+1)]ls.insert(0, 0)for i in range(1, num+1):for j in range(1, vol+1):print(i, j)# i = 1if ls[i][0] <= j:# 比较上一个状态dp_ls[i - 1][j]和当前状态的值，最大有最优# 当前状态的值 = 当前物品的价值 + (当前背包的体积-物品的体积)即上一个最优状态dp_ls[i-1]的列dp_ls[i-1][j-ls[i][0]]所对应的价值dp_ls[i][j] = max(dp_ls[i - 1][j], ls[i][1] + dp_ls[i-1][j-ls[i][0]])  #else:dp_ls[i][j] = dp_ls[i-1][j]print('最优矩阵：', dp_ls)print("最大价值：", dp_ls[-1][-1])