数学中的背包问题(1)

2016-04-23

Created by 高松

Copyrights © Yisa. All rights reversed.

More Notes From: https://github.com/Yisaer/Notes

概述：

背包问题是一个经典的数学问题，研究的是在已知每项物品的价值与所占容量时，如何计算出在各种情况下，在有限的背包容量里，放进的物品价值总和要最高。

我们将讨论：

01背包
完全背包
待续

01背包

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

这是最基本的背包问题，每个物品只有选或者不选两种选项。

假设物品一共有N件，那么在01背包的情况下，每件物品的情况只有选或者不选，那么通过基本的数学知识我们可以知道，所有的情况总共有2^N-1种情况，枚举每种状态，然后检查总重量是否合法，在所有可取的情况下选择总价值最高的情况即可。

然而这个方法的时间复杂度实在是太高了

而解决01背包的数学方法，则就是利用动态规划的思想。

假设有5件物品和一个容量为10的背包，

Index	Value	Weight
1	1	1
2	3	4
3	2	3
4	7	6
5	9	8

在这个问题中，通过目算我们可以得出，选取1 3 4或者2 4两个方法可以达到在可用容量内使得总价值和最高，但是从头开始重新去思考，当我们在考虑Index的前三号物品时，无论是选取1，3两件物品还是只选取2号一件物品，我们都花费了4个容量，得到了3点价值。然后在4，5号两个物品的选择上就显而易见了。从这里我们可以看出，在01背包里面，我们在容量为M的背包里选取N个物品的问题可以转换成在容量为J的背包里选取前I个物品的子问题，记作子问题F[i][j]，即重复子问题。

复杂度优化

在刚刚的问题中，无论我们是选择了1，3号物品还是2号物品，都不会对我选择4号物品产生影响，也就是说，我前面的子问题不会对后面的子问题产生影响，即无后效性。

从这里我们便可以看出，如果我们用F[i][j]来表示在前I件物品中花费了J容量所得到的价值，那么对于第I号物品来说，对于他的情况只有选或不选，如果没有选择第I号物品那么

F[i][j]=F[i-1][j]，即等于前I-1件物品花费了J容量的价值，

如果选择了第I号物品，那么

F[i][j]=F[i-1][j-W[i]]+v[i],其中w[i]表示物品i的容量，v[i]表示物品I的价值.

所以以伪代码的形式表示其状态方程为：

F[i][j] = max (F[i-1][j],F[i-1][j-w[i]]+v[i])

注意：这个等式极为重要，是所有背包问题的核心，我们会在后文中多次提及。

那么整个问题的解决就是求F[N][M],用伪代码则表示为：

For i = 1..N
    For j = M ...0
        If j<w[i]
            F[i][j] = F[i-1][j]
        End If
        F[i][j]= max (F[i-1][j],F[i-1][j-w[i]]+v[i]);
    End For
End For

为何程序两层循环是i从1->N，J是从M->0呢？

我们再回看刚刚的状态方程，当我们确定F[i][j]时，必须依赖F[i-1]的状态，所以I的循环是从1->N.

这样我们就能在O(NM)的复杂度内求出我们所需要的答案了。

空间度优化

让我们再来看回状态方程：

F[i][j] = max (F[i-1][j],F[i-1][j-w[i]]+v[i])

不难看出，当我们在求F[i][x]的时候，我们所依靠的是F[i-1][y]的数值，那么假设i=10的时候，那么我只需要i=9的时候的信息，而前面的信息则都不需要了。这就意味着我所需要的用到的信息只有当前状态，和前一个状态两种而已。那么这样子的话就只需要2*M的空间复杂度了。
然而事实上我们还可以进一步的优化，因为F[i]的状态依赖于F[i-1]，所以如果我们把第二重循环的顺序改为

For j = M...0

那么这就说明我们在计算F[i][j]的时候，F[i][j+1..M]已经经过计算了，也就意味着F[i-1][j..M]的空间没有用了，所以事实上我们一边计算，一边结果覆盖于用于存储的空间。最终空间复杂度简化的代码为：

For i = 0..N
    For j = M..0
        F[j] = max (F[j], F[j-w[i]]+v[i])
    End For
End For
Print F[M]

完全背包

完全背包和01背包十分相似，唯一的区别在于01背包里面每个物品只有1个，即你选或不选两种状态，完全背包则是每种物品都有无限个。

事实上，虽然完全背包每种物品都有无限个，但是由于背包容量有限，每个物品我们最多拿M/w[i]个。同样运用刚刚01背包的思想，将问题看成一个子问题，对于每件物品，我们可以选择不拿，或者是拿1~M[i]件，假设最优解的情况下，物品I拿k[i]件。

那么我们假设在子问题中，第I个物品选择K件，则可以得出状态方程：

F[i][j] = max (F[i][j] , F[i-1][j-w[i] k]+v[i] k)

用伪代码的形式则为：

For i = 0.. N
    For  j = 0 .. M
        For k = 0 .. M/w[i]
            F[i][j] =  max (F[i][j], F[i-1][j-w[i]*k]+v[i] * k)
        End For
    End For
End For

到了这一步，时间复杂性已经大大降下来了，不过如果我们继续研究这个等式，我们会发现这一个规律：

F[i][j] = max {F[i-1][j-w[i]*k]+v[i] * k}
                                            其中0<=k<=M/w[i]
F[i][j-w[i]] = max{F[i-1][j-w[i]*k]+v[i] * k} 
                                            其中1<=k<=M/w[i]
在这里面，我们不难看出
F=[i][j] = max{F[i][j-w[i]]+v[i],F[i-1][j]}

所以最后代码还可以优化为

For i =0.. N
    For j = 0 .. M
        if(w[i] < j)
            F[i][j] = F[i-1][j]
        else
            F[i][j] = max (F[i-1][j],F[i][j-w[i]]+v[i])
    End For
End FOr

最后同样的，当我们计算F[i]时，我们所需要的只是F[i-1]的信息，所以我们同样也可以将这个状态方程优化成空间O(m)的等式，与01背包相同，我就在这省去了。

总结

至此，01背包和完全背包就暂且说完了，事实上背包问题有更多更复杂的情况，也有更多黑科技的优化，这里我所说的是一种最基本也是最核心的思想理念。背包问题后面的类似于多重背包，等我有时间并且我也搞懂了的时候再写吧