作为动态规划(DP)中的经典问题背包问题，有以下三类子问题，分别为：0-1 背包问题、完全背包问题和多重背包问题。卜老师上课提到的主要为 0-1 背包问题。背包问题顾名思义，就是将一些物品放到一个背包中，背包对物体有重量限制，而我们需要的是背包中物体的总价值尽可能地多，其本质是有约束的优化问题。
    借用老师上课的图如下：
    转换为有约束的优化问题的数学表示如下：
    目标函数为每类物品价值总和，约束条件1为每类物品重量和不超过背包限重，约束条件2为每类物品的选取数量约束。不同的背包问题主要差别在于每类物品选取数量的约束，也就是  。
    显然，背包问题的本质是线性的有约束的优化问题，理论上也可以用线性规划解决，但这里只分析动态规划方法。
01 "0-1"背包问题
    0-1背包问题中，每类物品的选取只有：选-1or 不选-0，即  ，有约束优化问题，表示为如下：
    0-1 背包问题老师上课已经讲得很多了，这里直接给出子问题和状态转移方程：
    子问题：当背包容量为 j 时，前 i 个物品所能达到的最大价值。
    状态转移方程：面对背包容量为 j ，我们需要决策是不是需要放入第 i 个物品。如果包容量 j 放不下第 i 个物品，那么很简单，前 i 个物品所能达到的最大价值就是前 i-1个物品所能达到的最大价值；如果放得下，那么需要分析放第 i 个物品与不放第 i 个物品达到包容量 j 时的价值差异。公式表示如下
    借用卜老师课件的数据我们完善一下 OPT 表格如下：
    最后我们得到的最优的背包价值为$15,选择的物品为 2kg/$2、1kg/$2、1kg/$1 和4kg/$10。
    复杂度分析：OPT 表格中的状态数量为 W*N，W 为背包限重，N 为物品数量，状态转移复杂度为 O(1)，综合是时间复杂度为 O(W*N)，空间复杂度为 O(W*N)，类似背包问题都可以用一维数组更新代替二维数组(因为二维数组是从左往右从上到下按序生成状态值)，所以空间复杂度可以优化到 O(W)。
02 完全背包问题
    完全背包问题中，每类物品的选择都是不收限制的，也就是说  可以取到正无穷，因此有约束的优化问题表示如下：
    首先我们按照常规理解来做：
    子问题：当背包容量为 j 时，前 i 个物品所能达到的最大价值。
    状态转移方程：面对背包容量为 j ，我们需要决策放入几个第 i 个物品。如果包容量j放不下第 i 个物品，那么很简单，前 i 个物品所能达到的最大价值就是前i-1个物品所能达到的最大价值，与 0-1 背包问题一致；如果放得下，那么需要分析放 0,…,K 个第 i 个物品达到包容量 j 时的价值差异。
    公式表示如下：
    我们分析下这个时候的时间复杂度，OPT 表格中的状态数量仍然为 W*N，W 为背包限重，N 为物品数量，状态转移复杂度为 O(K)，其中  ，时间复杂度为  ，这显然是我们不希望看到的，我们希望仍然像 0-1 背包一样，状态转移复杂度为 O(1)。
    一种方法是利用本层 OPT 状态转移数，根据子问题描述，本层的 OPT 状态转移数  已经包含了我们需要决策的第 i 个物品，决策的问题从选择几个第 i 个物品变为是否再次放入一个第 i 个物品。状态转移复杂度重新降为 O(1)。
    因此我们将状态转移方程描述为如下：
    状态转移方程：面对背包容量为 j ，我们需要决策放入是否再次放入第 i 个物品。如果包容量 j 放不下第 i 个物品，那么前 i 个物品所能达到的最大价值就是前 i-1 个物品所能达到的最大价值；如果放得下，那么需要分析再次放入一个第 i 个物品达到包容量 j 时的价值与不放第 i 个物品达到的最大价值之间的差异。至于在放这个物品前已经放了几个第 i 个物品，由于已经在  经过了决策，因此在决策  时不需要考虑之前背包里已经存在的第 i 个物品的数目。
    表达式如下：
    同样用例题完成 OPT 表格
    最后我们得到的最优的背包价值为$36,选择的物品为 1kg/$2 选 3 件、4kg/$10 选 3 件。
    复杂度分析：OPT 表格中的状态数量为 W*N，W 为背包限重，N 为物品数量，状态转移复杂度为 O(1)，综合是时间复杂度为 O(W*N)，空间复杂度为 O(W*N)，同样，该背包问题都可以用一维数组更新代替二维数组，所以空间复杂度可以优化到 O(W)。
    值得注意的是：0-1 背包问题在遍历背包容量使可以正序也可以逆序，因为在生成OPT(i,j)使我们用到的只有上层状态数，而在完全背包问题下，遍历背包容量只可以正序，因为我们需要用到同层左侧的状态数，只有先生成左侧状态数，才能生成当前状态数。
03 多重背包问题
    多重背包问题提供了每种物品的数量限制，是介于 0-1 背包问题和完全背包问题中间的问题，有约束优化问题表示如下：
    我们同样可以按照常规方法去做：
    子问题：当背包容量为 j 时，前 i 个物品所能达到的最大价值。
    状态转移方程：面对背包容量为 j ，我们需要决策放入几个第 i 个物品。如果包容量 j 放不下第 i 个物品，前 i 个物品所能达到的最大价值就是前i-1个物品所能达到的最大价值；如果放得下，那么需要分析放 0,…,  个第 i 个物品达到包容量 j 时的价值差异。
    公式表示如下：
    同样分析下时间复杂度，OPT 表格中的状态数量仍然为 W*N，W 为背包限重，N 为物品数量，状态转移复杂度为   ， 时间复杂度为  
    https://www.kancloud.cn/kancloud/pack/70127  背包问题九讲中有对多重背包问题的优化，可以将时间复杂度降低至  。基本的策略是将第 i 种物品划分成若干件，划分标准在 blog 里有详细的说明。这里用 blog 中的一个例子，当    时，物品被划分为系数是 1,2,4,6 的四件物品，当你想取任意数目的  时，都可以用这四个系数组合而成。这样完成了将第 i 种物品分成了    种物品的 0-1 背包问题，复杂度从需要决策放入 0…13 件第 i 种物品变为决策是否放入第  种物品。
    同样用例题完成 OPT 表格，我们设置物品数量限制c=(3,3,2,3,2)
    最后我们得到的最优的背包价值为$29,选择的物品为 2kg/$2 选 2 件、1kg/$2 选 2 件、1kg/$1 选 1 件、4kg/$10 选 2 件。
04 混合背包问题
    混合背包问题将上述三种背包问题进行混合，即有的物品只能放一件，有的可以放多件，有的可以放无穷多件。很显然背包问题涉及的子问题都是完全一致的，即 OPT(i,j)中的状态数表示的含义是完全一致的。因此只需要按类选择不同的状态转移方程就行，如下所示：
05 结语
    背包问题作为动态规划中的基础问题，延伸出了许许多多多种多样的变形。通过对背包问题这一基础问题的学习和总结，或许能帮助我们加深对动态规划的理解，也能对那些看上去比较难的算法问题提供解题思路。

0-1背包问题是一类典型的组合优化问题，它要求找出n个物体的一个子集使其尽可能的装满容量为W的背包。他本质上是一个只有一个约束条件的0-1规划问题，在计算理论上属于NP完全问题，计算复杂性为o(2^n)。随着该问题的发展，产生了该问题的许多变形。例如：多选择背包问题；有界背包问题；无界背包问题；多约束背包问题等。

多选择背包问题定义为有附加约束条件的背包问题，该问题带有互不相关的多选择约束。该问题的特点是只有一个承重有限的背包，将要放入背包的物品被分为相互排斥的若干类，而每类中有若干不同的项目。

多约束背包问题也称为多维背包问题或者多背包问题，它是带有一组约束（重量 尺寸 可靠性等）的背包问题。该问题可以简单描述为n个物品要放入m个称重不同的背包，他与0-1背包问题不同的是，物品放入不同背包的重量是不同的。显然，在多约束背包的问题中，除了确定每个物品是否被放入背包之外，还需要确定他需要放入哪个背包。

多维多选择背包问题是一类特殊的0-1背包问题。问题的描述如下：存在m个背包，其称重分别是Wk（k=1，2，3…m）和n类物品，每类物品又分别有Ii（i=1,2,…n）个物品，其价值分别为Vij（j=1,2,…）而对每一个物品，由于其装入的背包不同而其重量也有所不同，分别为Wijk,该问题要求每一类只选择装入一个物品，在满足背包称重的限制下最大化装入背包的物品总价值。

1.参考资料

背包问题从简单到复杂有：

0-1背包：每种物品只能放入一次

完全背包：每种物品放入次数不限

多维费用背包：物品的费用可能有重量和体积等多个方面

复杂约束背包：背包的物品相互约束或依赖

推荐的材料是背包问题九讲，初步学习了0-1背包和完全背包问题。

 

2.  0-1背包问题

所有的背包问题都可以由0-1背包演化而来。

2.1 问题定义：

有一些物品，这些物品的重量为[cost i],对应的价值为[value i]，将它们装进容量为V的背包，求能获得的最大价值。

2.2 状态定义：

F[i,s]表示将前i件物品装进容量为s的背包时能获得的最大价值，则F[I,V]就是最优解。

2.3 状态转移方程：

F[i,s] = max{ F[i-1,s](不把第i件物品放入背包)，F[i-1,s-cost i]+value i(把第i 件物品放入背包)}

2.4 求解算法：



2.5 优化：

上述F数组是I*V，可以优化成一维数组。只要把重量的遍历顺序固定为V---cost i。因为每次更新时要用到前面的值，若从小到大更新，那么后边更新用到的前面的值是更新后的F[i，s-cost i]而非F[i-1, s-cost i]。实际上，求解时通常优先考虑一维数组。

算法改为：



 2.6 初始化：

若把题目的要求改为“装满背包时，最大价值多少”，则初始化F[0]=0,F[1..V]为-，因为s=0,问题可能有解，而没东西可放但是容量不为0，说明没有可行解，用无穷来表示这种状态。

其他的背包问题也要注意初始化问题，根据情况选为负无穷或正无穷。

 

3.  完全背包问题

3.1 定义

与0-1背包唯一的不同是每种物品数量不限。

3.2 状态转移方程

F[i,s] = max{ F[i-1,s](根本不把第i件物品放入背包)，F[i,s-cost i]+value i(把第i 件物品放入背包一次或多次)}唯一的区别在于第二项从i-1到i。

3.3 求解算法



 与0-1背包唯一的不同是重量的遍历顺序相反，完全背包的每一项更新要用到前边的更新后的值，所以要从小到大遍历，这样计算F[i,s]时，保证s-cost i的位置上是更新后的F[i, s-cost i]而非F[i-1, s-cost i]。

 

解背包问题的注意点

1.初始化

2.遍历顺序

3.数组的下标不要越界,比如 cost i可能大于V

4.  leetcode

416 0-1背包 装满

题目定义

非负数组分为两个子数组，两个子数组的和相等。给定一个数组，请问是否能分开。



代码

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums:
            return True
        if  len(nums)==1 :
            return True if nums[0]==0 else False
        nums_sum = 0
        for i in nums:
            nums_sum += i
        if nums_sum%2==1:
            return False
        v = nums_sum/2
        dp = [-1]*(v+1)#因为要装满，所以初始化为-1表示无解
        dp[0] = 1#初始化为1表示有解
        for i in nums:
            for idx in range(i,v+1)[::-1]:
                if dp[idx]==1 or dp[idx-i]==1:
                    dp[idx]=1
        return True if dp[-1]==1 else False

因为是要装满且是看问题有无解，所以初始化为-1表示无解，初始化为1表示有解。

322 完全背包 装满

问题定义

给一组人民币取值数组，给定一个目标值，求能用人民币数组表示的方案的最小张数，无解返回-1.



代码

class Solution(object):
    def coinChange(self, coins, amount):
        if not coins or amount<0:
            return -1
        dp = [10000]*(amount+1)
        dp[0] = 0
        for i in coins:
            for idx in range(i,amount+1):
                dp[idx]=min(dp[idx],dp[idx-i]+1)
        return dp[-1] if dp[-1]<10000 else -1

因为要求最小解，所以无解的初始值为正无穷。这是一个通用技巧。

474 0-1背包 二维约束

问题定义

给定0和1的个数，从一个字符串数组中选出不超过0，1的个数的最大字符串数。



 代码

class Solution(object):
    def findMaxForm(self, strs, m, n):
        if not strs:
            return 0
        dp = [[0 for i in range(n+1)] for j in range(m+1)]
        for s in strs:
            c0 = s.count('0')
            c1 = s.count('1')
            if c0>m or c1>n:
                continue
            for x in range(c0,m+1)[::-1]:
                for y in range(c1,n+1)[::-1]:
                    dp[x][y] = max(dp[x][y],dp[x-c0][y-c1]+1)
        return dp[m][n]

 与0-1背包的不同是F成了二维数组，分别表示两个约束的取值。也多了一层循环。

python新建二维list使用列表产生式，此处容易踩坑！！！而且行数列数顺序先后要注意！！！

377  交换内外层循环

问题定义

给出一个数组和目标值，求 和为目标值(正数)的组合数。注意，顺序不一样算两种解。



代码

from collections import deque
class Solution(object):
    def combinationSum4(self, nums, target):
        if not nums:
            return 0
        dp = [0]*(target+1)
        dp[0]=1
        for i in range(1,target+1):
            for num in nums:
                if i-num>=0:
                    dp[i]+=dp[i-num]
        return dp[-1]

494 巧妙转化为0-1背包

问题定义

给定数组，每个元素可以取为正或负，问有几种方法使数组所有元素和为目标值。



代码

class Solution(object):
    def findTargetSumWays(self, nums, S):
        if not nums:
            return 0
        sum_nums = sum(nums)
        if S>sum_nums or (sum_nums-S)%2==1:
            return 0
        target = (sum_nums-S)/2
        dp = [0]*(target+1)
        dp[0] = 1
        for num in nums:
            for idx in range(num,target+1)[::-1]:
                dp[idx] = dp[idx]+dp[idx-num]
        return dp[-1]

数组全取正数，和为sum_nums，与target差值的一半，就是取值为负的数的和。

问题变成了，选取数组的若干个数，使和为目标值（sum_nums-target)/2。

即0-1背包问题 装满。

1. 0-1背包问题
1.1 题目描述
有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做0-1背包，0表示不取，1表示取]
1.2思路
动态规划，根据动态规划解题步骤（建立模型、寻找约束条件、找子问题之间的的递推关系式、填表（区间模型）、得到解）找出0-1背包问题的最优解以及解组成。
1.3 步骤
首先定义：Vi表示标号为i物品的价值，Wi表示标号为i物品的体积。capacity为背包的最大容量。那么一个0-1背包问题的具体步骤如下：

建立模型，我们要求在物品总体积限制为capacity的情况下，尽可能装下价值高的物品组合，其模型如下：


寻找状态转换方程，即子问题之间的递推关系，我们令V(i,j)表示当前背包为容量 j，前 i 个物品最佳组合对应的价值最优解，那么就有两种可能：

a）包的容量比该商品体积小，即j < Vi，装不下第i个物品。此时背包容量为j，前i个物品的最优解与背包容量为j，前i-1个物品最佳组合对应的最优解是一样的，即V(i,j)=V(i-1,j)

b）当包的容量等于或大于该商品的体积，即j >= Vi，能装下第i个物品。那无非有两种情况，在前i个物品，背包容量为j的最优组合里有第i个物品，但同时占据了背包Wj个容量，V(i,j) = V(i-1,j-Wi)+Vi；在前i个物品，背包容量为j的最优组合里没有第i个物品，此时V(i,j) = V(i-1,j)。所以，根据最优性原理，背包容量为j，前i个物品的最优解V(i,j) 要取这两种情况的最大值，V(i,j) = max{V(i-1,j),V(i-1,j-Wi)+Vi},

由此可以得出递推关系式：


3. 根据递推公式进行逐行填表，初始化表V(i,o) = 0，V(0,j) = 0,表的列维度从0到n，行维度从0到capacity。

4.  根据填表过程，编写代码。
1.3 举例
有如下几种物品，物品的价值和体积如表所示：



首先定义：Vi表示标号为i物品的价值，Wi表示标号为i物品的体积。另外背包的总体积为10。
1.3.1 填表
填表过程如下：


1.4 python实现
def  zeroOneBag(num,capacity,weightList,valueList):
    valueExcel= [[0 for j in range(capacity + 1)] for i in range(num + 1)]
    for i in range(1,num+1):
        for j in range(1,capacity+1):
            valueExcel[i][j] = valueExcel[i - 1][j]
            if j >= weightList[i-1] and valueExcel[i][j] < (valueExcel[i - 1][j - weightList[i - 1]] + valueList[i - 1]):
                valueExcel[i][j] = (valueExcel[i - 1][j - weightList[i - 1]] + valueList[i - 1])
    return valueExcel
print(zeroOneBag(5,10,[2,2,6,5,4],[6,3,5,4,6]))
# 输出结果为：
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6], 
[0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9], 
[0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14],
[0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14], 
[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]]

因此该问题的价值最大组合为15。
1.4.1 算法优化
上面这种写法的时间复杂度为o（nc），空间复杂度也为o（nc）。时间复杂度不能在优化了，但是空间复杂度可以进行优化，使之降低到o（c）。
def zeroOneBagOpt(num,capacity,weightList,valueList):
    valueRes = [0 for i in range(capacity+1)]
    for i in range(1, num + 1):
        for j in range(capacity, 0, -1):
            if j >= weightList[i-1]:
                valueRes[j] = max(valueRes[j-weightList[i-1]]+valueList[i-1], valueRes[j])
        # i变一次，数组的更新一次，利用数组的不断更新，达到上面的方法动态规划的目的。
        # 当j遍历更新完一遍valueRes，valueRes就相当于完成上边方法中表第i+1行的填充.
        # 必须从后向前遍历和判断储存结果的数组，因为valueRes[j-weightList[i-1]]+valueList[i-1]就相当于V(i-1,j-Wi)+ Vi
        # 判断第i个物品是否是最优解的时候，需要以i-1的情况为基础，不能掺杂有关第i个物品的信息，
        # 如果从前往后遍历，那么valueRes[:j]的数是判断了i之后的，会产生错误。
        # 这里的value[j]即为上一次最佳结果，从后向前可以在遍历到j的未知的时候，不破坏j前面的上一次的最佳结果。
        # 
    return valueRes
print(zeroOneBagOpt(5,10,[2,2,6,5,4],[6,3,5,4,6]))
# 输出结果为：[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]

1.4.2 找到最佳组合的构成
通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：

V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
V(i,j)!=V(i-1,j)时，说明装了第i个商品，该商品是最优解组成的一部分，一定有V(i,j)=V(i-1,j-w(i))+v(i)，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
重复1,2，一直遍历到i＝0结束为止，所有解的组成都会找到。



最优解的组成由第1个，第2个，第5个。

def showRes(num,capacity,weightList,valueExcel):
    indexRes = []
    j = capacity
    for i in range(num,0,-1):
        if valueExcel[i][j] != valueExcel[i-1][j]:
            indexRes.append(i)
            j -= weightList[i-1]
    return indexRes
valueExcel = (zeroOneBag(5,10,[2,2,6,5,4],[6,3,5,4,6]))
print(showRes(5,10,[2,2,6,5,4],valueExcel))
# 输出结果为：[5, 2, 1]

2. 多重背包问题
2.1 问题详解

2.2 题目思路
2.2.1 一般思路


例如，第i种物品有3个，因此可以把这三个物品进行拆分，看作是不同种类的物体，不过是具有相同体积和价值的不同物品，通过拆分，就把可以放多个同种物品拆分成只能放0个或者一个“不同”物品的0-1背包问题。
2.2.1 python代码
# weightList：每种物品的体积
# valueList：每种物品的价值
# numList：每种物品的数量
def trans(weightList,valueList,numList):      # 转换函数 
    K = len(numList)
    newWeightList = []
    newValueList = []
    num = sum(numList)
    for i in range(K):
        for j in range(numList[i]):
            newWeightList.append(weightList[i])
            newValueList.append(valueList[i])
    return num,newValueList,newWeightList
def zeroOneBag(numList,capacity,weightList,valueList):
 	# 先将多重问题转成0-1问题，利用0-1问题的代码。
    num,newValueList,newWeightList = trans(weightList,valueList,numList)
    valueExcel= [[0 for j in range(capacity + 1)] for i in range(num + 1)]
    for i in range(1,num+1):
        for j in range(1,capacity+1):
            valueExcel[i][j] = valueExcel[i - 1][j]
            if j >= newWeightList[i-1] and valueExcel[i][j] < (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1]):
                valueExcel[i][j] = (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1])
    return valueExcel
print(zeroOneBag([2,5,10],8,[2,2,1],[20,10,6]))
# 输出结果：
#[[0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 20, 20, 20, 20, 20, 20, 20], 
# [0, 0, 20, 20, 40, 40, 40, 40, 40],
# [0, 0, 20, 20, 40, 40, 50, 50, 50],
# [0, 0, 20, 20, 40, 40, 50, 50, 60],
# [0, 0, 20, 20, 40, 40, 50, 50, 60],
# [0, 0, 20, 20, 40, 40, 50, 50, 60],
# [0, 0, 20, 20, 40, 40, 50, 50, 60],
# [0, 6, 20, 26, 40, 46, 50, 56, 60],
# [0, 6, 20, 26, 40, 46, 52, 56, 62],
# [0, 6, 20, 26, 40, 46, 52, 58, 62],
# [0, 6, 20, 26, 40, 46, 52, 58, 64],
# [0, 6, 20, 26, 40, 46, 52, 58, 64],
# [0, 6, 20, 26, 40, 46, 52, 58, 64],
# [0, 6, 20, 26, 40, 46, 52, 58, 64],
# [0, 6, 20, 26, 40, 46, 52, 58, 64],
# [0, 6, 20, 26, 40, 46, 52, 58, 64],
# [0, 6, 20, 26, 40, 46, 52, 58, 64]]

最终的最大价值为64。和0-1背包问题一样，可以对空间进行优化，这里就省略了。
2.2.2 优化
利用一般的思路讲多重背包问题转化成0-1背包问题进行解决，某种物品有多少个就要拆分成多少个不同的物品，这会增加时间复杂度和空间复杂度。因此我们可以利用另一种分解方法：二进制分解


二进制分解代码
def binaryDecomposition(n):  # 二进制分解
     k = 0
     res = []
     while n - 2**(k+1) + 1  > 0:
         res.append(2**k)
         k += 1
     res.append(n-2 ** (k) + 1)
     return res

如果第i种物品有13个，根据这种思路，13拆分成1,2，4,6。只需要将这种物品拆分成4个物品，这四个物品的体积和价值分别是（Wi,Vi），（2Wi,2Vi），（4Wi,4Vi），（6Wi,6Vi），而不是13个物品，这就降低了时间复杂度和空间复杂度。
2.2.2 python代码
# optimization
def binaryDecomposition(n):  # 二进制分解
     k = 0
     res = []
     while n - 2**(k+1) + 1  > 0:
         res.append(2**k)
         k += 1
     res.append(n-2 ** (k) + 1)
     return res
def trans(weightList,valueList,numList):
    newWeightList = []
    newValueList = []
    for i in range(len(numList)):
        for j in binaryDecomposition(numList[i]):
            newWeightList.append(j * weightList[i])
            newValueList.append(j * valueList[i])
    num = len(newValueList)
    return num,newValueList,newWeightList
def  zeroOneBag(numList,capacity,weightList,valueList):
    num,newValueList,newWeightList = trans(weightList,valueList,numList)
    valueExcel= [[0 for j in range(capacity + 1)] for i in range(num + 1)]
    for i in range(1,num+1):
        for j in range(1,capacity+1):
            valueExcel[i][j] = valueExcel[i - 1][j]
            if j >= newWeightList[i-1] and valueExcel[i][j] < (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1]):
                valueExcel[i][j] = (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1])
    return valueExcel
print(zeroOneBag([2,5,10],8,[2,2,1],[20,10,6]))
# 输出结果为：
[[0, 0, 0, 0, 0, 0, 0, 0, 0],
#[0, 0, 20, 20, 20, 20, 20, 20, 20],
#[0, 0, 20, 20, 40, 40, 40, 40, 40],
#[0, 0, 20, 20, 40, 40, 50, 50, 50],
#[0, 0, 20, 20, 40, 40, 50, 50, 60],
#[0, 0, 20, 20, 40, 40, 50, 50, 60],
#[0, 6, 20, 26, 40, 46, 50, 56, 60],
#[0, 6, 20, 26, 40, 46, 52, 58, 62],
#[0, 6, 20, 26, 40, 46, 52, 58, 64],
#[0, 6, 20, 26, 40, 46, 52, 58, 64]]

通过输出结果也可以看出，表的维度比上一种方法要低。最终的最佳组合的价值为64。
3.完全背包问题
3.1 问题描述

3.2.1 思路
完全背包问题和多重背包问题以及0-1背包问题的唯一不同就在于在背包容量允许的情况下，可以在背包里放无限个同一种物品。

下面是0-1背包问题的递推公式：



我们仍然令V(i,j)表示当前背包为容量 j，前 i 个物品最佳组合对应的价值最优解。那么我们可以根据这个0-1背包问题的状态转换方程通过变化，得到完全背包问题的递推公式。


3.2 python代码
def compKnap(num,capacity,weightList,valueList):
    valueExcel = [[0 for j in range(capacity + 1)] for i in range(num + 1)]
    for i in range(1, num + 1):
        for j in range(1, capacity + 1):
            for k in range((j // weightList[i - 1]) + 1):
                if valueExcel[i][j] < (valueExcel[i - 1][j - k*weightList[i - 1]] + k*valueList[i - 1]):
                    valueExcel[i][j] = (valueExcel[i - 1][j - k * weightList[i - 1]] + k*valueList[i - 1])
    return valueExcel
# print(compKnap(5,16,[5,4,7,2,6],[12,3,10,3,6]))
"""
输出结果为：
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 24, 24, 24, 24, 24, 36, 36],
 [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 24, 24, 24, 24, 27, 36, 36],
 [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 24, 24, 24, 24, 27, 36, 36],
 [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36],
 [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36]]
"""

3.2.2 优化
和0-1背包问题一样，完全背包问题也可以通过二进制分解来进行拆分，来降低时间复杂度和空间复杂度。同时，还可以优化，将其优化成和相同条件下0-1背包问题时间复杂度、空间复杂度一样的算法。

其方法和0-1背包问题的优化方法一样。都是借助一个一维数组。
3.2.2 python 代码
def compKnapOpt(num,capacity,weightList,valueList):
    valueExcel = [0 for j in range(capacity + 1)]
    for i in range(1, num + 1):
        for j in range(1, capacity + 1):
            if weightList[i-1]<=j:
                valueExcel[j] = max(valueExcel[j - weightList[i - 1]] + valueList[i - 1], valueExcel[j])
    return valueExcel
print(compKnapOpt(5,16,[5,4,7,2,6],[12,3,10,3,6]))
# 输出结果：
[0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36]