python -- 0/1背包问题（动态规划-dict）
16lz
2021-01-22
#! /usr/bin/env python3动态规划：先解决子问题,再逐步解决大问题，每个动态规划算法都从一个网格开始
# -*- coding: utf-8 -*-
def getMaxValueOfPackage(N, C, W, V): # 商品的种类, 背包的容量, 每样商品的容量, 每样商品的价值
# 构造网格--初始化
cell = [ [ 0 for i in range(C+1)] for j in range(N+1)]
for i in range(1, N+1):
for j in range(1, C+1):
cell[i][j]=cell[i-1][j]
if j >= W[i-1] and cell[i][j] < V[i-1] + cell[i-1][j-W[i-1]]:
cell[i][j] = V[i-1] + cell[i-1][j-W[i-1]]
# 显示网格
for i in range(N+1):
print(cell[i])
return cell
def show(N, C, W, Cell, Goods): # 商品的种类, 背包的容量, 每样商品的容量, 已经规划好的网格, 商品列表
print('最大价值为:', Cell[N][C])
processed = [False for i in range(N)]
cap = C
for i in range(N, 0, -1):
if Cell[i][cap] != Cell[i-1][cap]:
processed[i-1]=True
cap-=W[i-1]
print('选择的物品为:', end='')
for i in range(N):
if processed[i]:
print("%s, " % Goods[i], end='')
print('剩余空间为：', cap)
if __name__ == "__main__":
capacity = 4
goods = {}
goods["吉他"] = [1, 1500]
goods["音响"] = [4, 3000]
goods["笔记本"] = [3, 2000]
goods["IPhone"] = [1, 2000]
#goods["MP3"] = [1, 1000]
goods_keys = list(goods.keys()) # 商品列表
goods_types = len(goods_keys)
goods_values = list(goods.values()) # 每样商品的容量, 每样商品的价值
weights = [item[0] for item in goods_values] # 每样商品的容量
values = [item[1] for item in goods_values] # 每样商品的价值
print(goods)
cc = getMaxValueOfPackage(goods_types, capacity, weights, values)
show(goods_types, capacity, weights, cc, goods_keys)
1. 问题:沿着一列往下走时,最大价值有可能降低吗?
不可能。每次迭代时,你都存储当前的最大价值。最大价值不可能比以前低!
2. 假设你还可偷另外一件商品——MP3播放器,它重1磅,价值1000美元。你要偷吗?
运行程序即可知道答案
3. 行的排列顺序发生变化时结果将如何？
答案没有变化。也就是说,各行的排列顺序无关紧要。
4. 可以逐列而不是逐行填充网格吗？
自己动手试试吧!就这个问题而言,这没有任何影响,但对于其他问题,可能有影响。
5. 增加一件更小的商品将如何呢？
假设你还可以偷一条项链,它重0.5磅,价值1000美元。前面的网格都假设所有商品的重量为整数,但现在你决定把项链给偷了,因此余下的容量为3.5磅。在3.5磅的容量中,可装入的商品的最大价值是多少呢?
不知道!因为你只计算了容量为1磅、2磅、3磅和4磅的背包可装下的商品的最大价值。现在,你需要知道容量为3.5磅的背包可装下的商品的最大价值。
由于项链的加入,你需要考虑的粒度更细,因此必须调整网格。
6. 可以偷商品的一部分吗？
答案是没法处理。使用动态规划时,要么考虑拿走整件商品,要么考虑不拿,而没法判断该不该拿走商品的一部分。但使用贪婪算法可轻松地处理这种情况!首先,尽可能多地拿价值最高的商品;如果拿光了,再尽可能多地拿价值次高的商品,以此类推。
7. 处理相互依赖的情况?
没办法建模。动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用 。
8. 最优解可能导致背包没装满吗?
完全可能。假设你还可以偷一颗钻石。这颗钻石非常大,重达3.5磅,价值100万美元,比其他商品都值钱得多。你绝对应该把它给偷了!但当你这样做时,余下的容量只有0.5磅,别的什么都装不下。
# 旅游行程最优化
r'''假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中每样东西都有相应的价值,价值越大意味着越重要:
水(重3磅,价值10);
书(重1磅,价值3)
食物(重2磅,价值9);
夹克(重2磅,价值5);
相机(重1磅,价值6)。
请问携带哪些东西时价值最高?
启示》》》
动态规划可帮助你在给定约束条件下找到最优解。在背包问题中,你必须在背包容量给定的情况下,偷到价值最高的商品。
在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。
单元格中的值是什么? 通常就是你要优化的值
如何将这个问题划分为子问题? 限制条件从小到大
网格的坐标轴是什么? x（外循环）可选列表， y（内循环）限制条件
'''
def getMaxValueOfPackage(N, C, W, V): # 名胜的数量, 旅游时间, 每个名胜所花时间, 每个名胜的评分
# 构造网格--初始化
cell = [ [ 0 for i in range(C+1)] for j in range(N+1)]
for i in range(1, N+1):
for j in range(1, C+1):
cell[i][j]=cell[i-1][j]
if j >= W[i-1] and cell[i][j] < V[i-1] + cell[i-1][j-W[i-1]]:
cell[i][j] = V[i-1] + cell[i-1][j-W[i-1]]
# 显示网格
for i in range(N+1):
print(cell[i])
return cell
def show(N, C, W, Cell, Goods): # 名胜的数量, 旅游时间, 每个名胜所花时间, 已经规划好的网格, 名胜列表
print('最大价值为:', Cell[N][C])
processed = [False for i in range(N)]
cap = C
for i in range(N, 0, -1):
if Cell[i][cap] != Cell[i-1][cap]:
processed[i-1]=True
cap-=W[i-1]
print('选择的地方为:', end='')
for i in range(N):
if processed[i]:
print("%s, " % Goods[i], end='')
print('剩余时间啊为：', cap)
if __name__ == "__main__":
days = 4
monument = {}
monument["威斯敏斯特教堂"] = [1, 7] # 限制条件， 最大值项
monument["环球剧场"] = [1, 6]
monument["英国国家美术馆"] = [2, 9]
monument["大英博物馆"] = [4, 9]
monument["圣保罗大教堂"] = [1, 8]
monument_keys = list(monument.keys()) # 名胜列表
monument_types = len(monument_keys)
monument_values = list(monument.values()) # 每个名胜所花时间, 每个名胜的评分
weights = [item[0] for item in monument_values] # 每个名胜所花时间
values = [item[1] for item in monument_values] # 每个名胜的评分
print(monument)
cc = getMaxValueOfPackage(monument_types, days, weights, values)
show(monument_types, days, weights, cc, monument_keys)