Python处理01背包问题
问题描述：01背包是在N件物品取出若干件放在空间为V的背包里，每件物品的体积为V1，V2……Vn，与之相对应的价值为P1,P2……Pn（所有的体积值均为整数）。环境工具：win7 python2.7
解决过程：考虑用动态规划的方法来解决
阶段 【在前N件物品中，选取若干件物品放入背包中】
状态 【在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值】
决策 【第N件物品放或者不放】
可以写出动态转移方程
用f表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
f=max{f+Pi (j>=Wi), f}
基本上所有跟背包相关的问题的方程都是由它衍生出来的。
演变解释@考虑在V的空间下，放入N件物品能获得最大价值（前N-1物品是最大价值的，第N件产品可以放进去）
=》考虑在V - Vn的空间下，放入N-1件物品能获得最大价值（前N-2物品是最大价值的，第N-1件物品可以放进去）
=》考虑在V - Vn-1 - Vn的空间下，放入N-2件物品能获得最大价值（前N-3物品是最大价值的，第N-2件物品可以放进去）
......
=》考虑在V - V3 - V4... - Vn的空间下，放入2件物品能获得最大价值（前1物品是最大价值的，第2件物品可以放进去）
=》考虑在V - V2 - V3 - V4... - Vn的空间下，放入1件物品能获得最大价值（前0物品的价值是0，第1件物品可以放进去）
源代码如下
#! C:\\Python27\\python.exe
# -*- coding:utf-8 -*-
import copy
class DynamicBag:
def __init__(self, limitVolume, itemsVolume, itemsValue):
self.limitVolume = limitVolume #最大体积上限，容积
self.itemsVolume = itemsVolume #所有项的每项的体积
self.itemsValue = itemsValue #所有项的每项的价值
self.resultSumVolume = 0 #最大价值的占用体积
self.resultSumValue = 0 #最大价值
self.resultItemsVolume = [] #最大价值的每项体积
self.resultItemsValue = [] #最大价值的每项价值
def dynamicSuitResult(self):
itemsCount = len(self.itemsVolume)
if itemsCount == len(self.itemsValue):
allItems = [] #所有项的下标
self.itemsVolume.append(0) #添加0项，方便计算
self.itemsValue.append(0)
itemsCount = itemsCount + 1
for k in range(itemsCount):
allItems.append(k)
(self.resultSumVolume, self.resultSumValue, resulItems) = self.dynamic01Bag(allItems, limitVolume, allItems)#获得最大价值的占用体积，最大价值，组成项的索引
del resulItems#去除0项索引
for k in resulItems:
self.resultItemsVolume.append(self.itemsVolume)#根据最大价值的组成项的索引获得项
self.resultItemsValue.append(self.itemsValue)
else:
print("args error!")
return (self.resultSumVolume, self.resultSumValue, self.resultItemsVolume, self.resultItemsValue)#返回 最大价值的占用体积，最大价值，最大价值的每项体积，最大价值的每项价值
def dynamic01Bag(self, oneItem, limitVolume, allItems):
suitSumVolume = 0 #当前项的最大价值占用体积
suitSumValue = 0 #当前项的当前最大价值
suitItems = [] #当前项的当前最大价值的组成项的索引
partItems = copy.copy(allItems)
del partItems#去掉当前项
if len(partItems)==1:#前一项只有一项
if limitVolume < self.itemsVolume]:#容积小于前一项
return (suitSumVolume, suitSumValue, suitItems)
elif limitVolume >= (self.itemsVolume] + self.itemsVolume):#容积大于等于前一项+当前项
suitSumVolume = self.itemsVolume] + self.itemsVolume
suitSumValue = self.itemsValue] + self.itemsValue
suitItems.append(oneItem)
suitItems.append(partItems)
return (suitSumVolume, suitSumValue, suitItems)
else:#容积大于等于前一项，小于前一项+当前项
suitSumVolume = self.itemsVolume]
suitSumValue = self.itemsValue]
suitItems.append(partItems)
return (suitSumVolume, suitSumValue, suitItems)
else:#前一项有多项
suitVolume1 = 0
suitValue1 = 0
suitVolume2 = 0
suitValue2 = 0
suitIndex1 = 0
suitIndex2 = 0
result = []
for k in range(len(partItems)):
(aSumVolume, bSumValue, cItems)=self.dynamic01Bag(partItems, limitVolume - self.itemsVolume, partItems)#对多个前一项的每项求最大值
result.append((aSumVolume, bSumValue, cItems))
if (aSumVolume + self.itemsVolume) <= limitVolume:#存在容积大于等于前一项+当前项的情况，获取最大的前一项+当前项
if (bSumValue + self.itemsValue) > suitValue1:#对多个前一项的最大值，求最优
suitVolume1 = aSumVolume + self.itemsVolume
suitValue1 = bSumValue + self.itemsValue
suitIndex1 = k
if bSumValue > suitValue2:#容积小于所有的前一项+当前项情况下使用，获取最大的前一项
suitVolume2 = aSumVolume
suitValue2 = bSumValue
suitIndex2 = k
if suitValue1 > 0:#存在容积大于等于前一项+当前项的情况，获取最大的前一项+当前项
suitSumVolume = suitVolume1
suitSumValue = suitValue1
suitItems.append(oneItem)
suitItems.extend(result)
return (suitSumVolume, suitSumValue, suitItems)
else:#容积小于所有的前一项+当前项情况下使用，获取最大的前一项
suitSumVolume = suitVolume2
suitSumValue = suitValue2
suitItems.extend(result)
return (suitSumVolume, suitSumValue, suitItems)
#算法验证
if __name__ == '__main__':
limitVolume = 20#体积上限
itemsVolume = #单个总体积
itemsValue = #单个总价值
hk01bag = DynamicBag(limitVolume, itemsVolume, itemsValue)
(resultSumVolume, resultSumValue, resultItemsVolume, resultItemsValue) = hk01bag.dynamicSuitResult()
print '最大价值：'+str(resultSumValue)
print '最大价值的单个价值：'
print resultItemsValue
print '最大价值的总体积：'+str(resultSumVolume)
print '最大价值的单个总体积：'
print resultItemsVolume
页:
[1]