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