背包问题

0-1背包问题

基本模型：有n种物品，1个背包；n种物品各有价值 与重量 ，背包有容量限制 。求用该背包放哪些物品使得价值最高，且每种物品只有一个。
即解题思路是：对于每种件物品，要么放入背包，要么不放两种状态。故称零幺背包问题。

解题方法：动态规划思想（拒绝暴力）

每一步的新状态（针对每种物件）为：维持原状态或取该物件，以此不断递归。
即状态转移基本模型为：

其中表示物品的序号， 表示背包空间， 表示当前总价值。 表示上一状态总价值，表示取当前物品，加上取该物品后，背包剩余空间时的最优状态（因为每一步都是取最优，整体亦是最优）。
具体解题时，用一个二维表表示，行为物品，列为空间，按行依次遍历。

例题：

有4件物品，重量分别为 ，价值分别为，背包空间为5。
按以上公式结合二维表解题

bag.jpg

解题分析：右下角的7为最终结果，其由第三行的7通过得来。而第三行的7是通过 得来。直观理解为把第三件物品放入包后（价值为4），包剩下空间2，那么加上背包空间为2时的最优状态，即第二行第三列黑色的3，依次思想解题。

伪代码如下：

def Bag(w,v,W):
    #初始化第一行
    for j in range(W+1):
        bag[0][j]=0
    #初始化第一列
    for i in range(len(v)+1):
        bag[i][0]=0

    for i in range(1,len(v)+1):
        for j in range(1,W+1):
            if j<w[i]:
                bag[i][j]=bag[i-1][j]
            else:
                bag[i][j]=max(bag[i-1][j],bag[i-1][j-w[i]]+v[i])
    return bag[len(v)][W]

---

背包问题的空间优化

上述解法采用二维数组，其空间复杂度为 （二维表的空间）。而仔细观察模型解题过程，其实 只是与 有关，换言之，当前数组只与上一数组的值有关，与无关，即言其他的其实不用存储。只需要有一个一维数组存储即可。
伪代码如下：

def bag(w,v,W):
    count=len(w)
    dp=[0 for i in range(W+1)]

    for i in range(count):
        j=W
        while not j<w[i]:
            dp[j]=max(dp[j],dp[j-w[i]]+v[i])
            j-=1
    return dp[-1]

注意：用一维数组表示时，必须逆序更新。
其直观理解为：一个背包的当前状态（当前剩余空间），取决于装下当前物品后价值是否更高。若是，则更新，若不是，便保持原状。

---

完全背包问题

问题模型：在零幺背包问题的基础上，修改为每种物品数量有任意个。
即背包允许放多个同种物品，使得总价值最优，此种条件下，每一种物品便不止只有两种状态，而有 种状态，其中 满足 。

那么状态转移方程便改为：

伪代码为：

def Bag(w,v,W):
    #初始化第一行
    for j in range(W+1):
        bag[0][j]=0
    #初始化第一列
    for i in range(len(v)+1):
        bag[i][0]=0

    for i in range(1,len(v)+1):
        for j in range(1,W+1):
            if j<w[i]:
                bag[i][j]=bag[i-1][j]
            else:
                for k in range(W//w[i]):
                    bag[i][j]=max(bag[i-1][j],bag[i-1][j-k*v[i]]+k*v[i])
                
    return bag[len(v)][W]

但是这样搞时间复杂度非常高：为 ，所以为了人与电脑和谐相处，必须优化。

---

完全背包问题时间优化

实质上，问题仅是转化为：从取0个当前物品，取1个当前物品......取k个当前物品这k+1个情况中，选择价值最大一那个，即

其中 满足。换言之，可选方案如下：

亦可写成

利用换元法：令得以上方程，除第零行外，其余可表示为

将代回去，得到 ，



伪代码如下：

def Bag(w,v,W):
    #初始化第一行
    for j in range(W+1):
        bag[0][j]=0
    #初始化第一列
    for i in range(len(v)+1):
        bag[i][0]=0

    for i in range(1,len(v)+1):
        for j in range(1,W+1):
            if j<w[i]:
                bag[i][j]=bag[i-1][j]
            else:
                bag[i][j]=max(bag[i-1][j],bag[i][j-w[i]]+v[i])
                
    return bag[len(v)][W]

---

多重背包问题

多重背包问题与完全背包问题类似，只不过是每件物品有数量限制，而非完全背包的无限个。
即问题描述为：有一个背包载重为 ， 种物品质量和价值分别为 ，且每种物品各有 个。求背包价值最高状态。

其实，解题思路仅是从完全背包问题基础上，对数量加一限制即可

然而这样时空复杂度都较高，需要优化

多重背包二进制优化

此种优化主要是将 分解，类似于快乘法的思想。将 分解成用2的次方之和表示，然后结合一维数组的优化。得以下伪代码

def MulBag(w,v,num,W):
    count=len(w)
    dp=[0 for in range(W+1)]

    for i in range(count):
        k=1
        while num[i]:
            if num[i]<k:
                k=num[i]#不能用2的整次幂表示
            num[i]=num[i]-k#剩下几个
            j=W
            while not j<w[i]:
                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])
                j=-1
            k=k<<1#算术左移，即乘二