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