421443160730094203.jpg
背包问题(0—1背包)
有N件物品，背包的最大承重为M，每件物品的数量均为1，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。
动态规划思想：
-
状态
当前背包还可以承受的最大重量，当然初始状态就是M； -
子问题
对于某件物品i而言，子问题可理解为选择这件物品，或者是不选择这件物品。 -
状态转移方程
image
其中V(W)表示背包已装物品重量为M时的最大价值，上述比较的两者，前者表示不装第i件物品时，背包已经承载物品的最大价值，后者表示装了第i件物品后，剩余的空间可以装载物品的最大价值与第i件物品价值的和。两者取最大，则可保证最后的方案是最优的。
-
边界条件
V(0)=0
图示：
image
下面给出基于Python3的代码
weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
maxweight = 8
# 只输出最大价值
def ZeroOnePack_Simple(W, V, MW): # 0-1背包
# 存储最大价值的一维数组
valuelist = [0] * (MW + 1)
# 开始计算
for ii in range(len(W)): # 从第一个物品
copyvalue = valuelist.copy()
for jj in range(MW + 1): # 从重量0
if jj >= W[ii]: # 如果重量大于物品重量
copyvalue[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj]) # 选中第ii个物品和不选中，取大的
valuelist = copyvalue.copy() # 更新
return '最大价值：', valuelist[-1]
# 也输出选择物品的编号
def ZeroOnePack(W, V, MW): # 0-1背包
# 存储最大价值的一维数组
valuelist = [0] * (MW + 1)
# 存储物品编号的字典
codedict = {i: [] for i in range(0, MW + 1)}
# 开始计算
for ii in range(len(W)): # 从第一个物品
copyvalue = valuelist.copy()
copydict = codedict.copy()
for jj in range(MW + 1): # 从重量0
if jj >= W[ii]: # 如果重量大于物品重量
copyvalue[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj]) # 选中第ii个物品和不选中，取大的
# 输出被选中的物品编号
if copyvalue[jj] > valuelist[jj]:
copydict[jj] = [ii]
for hh in codedict[jj - W[ii]]:
copydict[jj].append(hh)
codedict = copydict.copy() # 更新
valuelist = copyvalue.copy() # 更新
print('所需物品：', sorted([1 + code for code in codedict[MW]]))
return '最大价值：', valuelist[-1]
print(ZeroOnePack_Simple(weight, value, maxweight))
image
背包问题(完全背包)
有N件物品，背包的最大承重为M，每件物品的数量无限，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。
这个和0-1背包的最大区别在于：每计算一次V值，就立即更新。其状态转移方程和0-1背包相同，因为有实时的更新V值，就相当于同一个物品可以多次选取。
下面给出基于Python3的代码
weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
maxweight = 8
# 只输出最大价值
def CompletePack_Simple(W, V, MW):#完全背包
#存储最大价值的一维数组
valuelist = [0] * (MW + 1)
#开始计算
for ii in range(len(W)):#从第一个物品
for jj in range(MW + 1):#从重量0
if jj >= W[ii]:#如果重量大于物品重量
valuelist[jj] = max(valuelist[jj - W[ii]] + V[ii], valuelist[jj])#选中第ii个物品和不选中，取大的
return '最大价值：', valuelist[-1]
# 也输出选择物品的编号以及个数
def CompletePack(W, V, MW):#完全背包
#存储最大价值的一维数组
valuelist = [0] * (MW + 1)
#存储物品编号的字典
codedict = {i: [] for i in range(0, MW + 1)}
#开始计算
for ii in range(len(W)):#从第一个物品
copyvalue = valuelist.copy()
copydict = codedict.copy()
for jj in range(MW + 1):#从重量0
if jj >= W[ii]:#如果重量大于物品重量
cc = copyvalue[jj]
copyvalue[jj] = max(copyvalue[jj - W[ii]] + V[ii], copyvalue[jj])#选中第ii个物品和不选中，取大的
#输出被选中的物品编号
if copyvalue[jj] > cc:
copydict[jj] = [ii]
for hh in copydict[jj - W[ii]]:
copydict[jj].append(hh)
codedict = copydict.copy()#更新
valuelist = copyvalue.copy()#更新
result = ''
for hcode in sorted(list(set(copydict[MW]))):
result += '物品：%d :%d个' % (hcode + 1, copydict[MW].count(hcode))
print(result)
return '最大价值：', valuelist[-1]
print(CompletePack_Simple(weight, value, maxweight))
image
背包问题(多重背包)
有N件物品，背包的最大承重为M，每件物品的数量集合为C，价值集合为V，重量集合为W，计算该背包可以承载的物品的最大价值。
这个和完全背包的最大区别在于：完全背包因为没有物品数量的限制，因此可以无限叠加。因此需要加上对数量的限制语句。
下面是基于Python3的代码
weight = [4, 3, 2, 6, 5]
value = [3, 4, 6, 7, 9]
count = [3, 2, 1, 1, 0]
maxweight = 8
# 只输出最大价值
def MultiplePack_Simple(W, V, C, MW): # 多重背包
# 存储最大价值的一维数组
valuelist = [0] * (MW + 1)
# 开始计算
for ii in range(len(W)): # 从第一个物品
copyvalue = valuelist.copy()
for jj in range(MW + 1): # 从重量0
if jj >= W[ii]: # 如果重量大于物品重量
for gg in range(C[ii] + 1): # 限制=数量
if gg * W[ii] <= jj:
copyvalue[jj] = max(valuelist[jj - gg * W[ii]] + gg * V[ii], copyvalue[jj])
valuelist = copyvalue.copy() # 更新
return '最大价值：', valuelist[-1]
# 也输出编号以及个数
def MultiplePack(W, V, C, MW): # 多重背包
# 存储最大价值的一维数组
valuelist = [0] * (MW + 1)
# 存储物品编号的字典
codedict = {i: [] for i in range(0, MW + 1)}
# 开始计算
for ii in range(len(W)): # 从第一个物品
copyvalue = valuelist.copy()
copydict = codedict.copy()
# 存储物品所用数量的一维数组
number = [0] * (MW + 1)
for jj in range(MW + 1): # 从重量0
if jj >= W[ii]: # 如果重量大于物品重量
for gg in range(C[ii] + 1): # 限制数量
cc = copyvalue[jj]
if gg * W[ii] <= jj:
copyvalue[jj] = max(valuelist[jj - gg * W[ii]] + gg * V[ii], copyvalue[jj])
if copyvalue[jj] > cc:
number[jj] += 1
copydict[jj] = number[jj] * [ii]
for hh in codedict[jj - number[jj] * W[ii]]:
copydict[jj].append(hh)
codedict = copydict.copy() # 更新
valuelist = copyvalue.copy() # 更新
result = ''
for hcode in sorted(list(set(copydict[MW]))):
result += '物品：%d: %d个。' % (hcode + 1, copydict[MW].count(hcode))
print(result)
return '最大价值：', valuelist[-1]
print(MultiplePack_Simple(weight, value, count, maxweight))
扫描下方二维码或者微信公众号直接搜索”Python范儿“，关注微信公众号pythonfan， 获取更多实例和代码。
pythonfan.jpg
网友评论