在昨天我已经很详细的讲解过01背包的动态规划问题了，今天我讲解的是完全背包的问题，这是01背包的详解：
先看问题：在n种物品中选取若干件（同一种物品可多次选取）放在空间为v的背包里，每种物品的体积为c1，c2，…，cn，与之相对应的价值为w1,w2，…，wn.求解怎么装物品可使背包里物品总价值最大
看完这个问题，你也许会觉得这个不就是01背包的升级版吗，其实就是这样，完全背包问题与01背包问题的区别在于完全背包每一件物品的数量都有无限个，而01背包每件物品数量只有1个
所以说与它相关的策略已经不是只有取和不取这两种策略了，而是有取0件、取1件、取2件……等等很多种策略
如果我们用和01背包一样的状态，f[i][v]表示前i种物品恰放入一个容量为v的背包的最大价值，那我们应该用k表示当前容量下可以装第i种物品的件数，那么k的范围应该是0≤k≤v/c[i]，
既然要用当前物品i把当前容量装满，那需要0≤k≤v/c[i]件，其中k表示件数。
下面给出状态转移方程：
f[i][j] = max{f[i][j],f[i-1][j - k * c[i]] + k * w[i]}(0<=k*c[i]<=v)
贴一段代码：
for (int i = 1; i < n; i++){ for (int j = 1; j <= v; j++){ for (int k = 0; k*c[i] <= j; k++){ if(c[i]<=j)/*如果能放下*/ f[i][j] = max{f[i][j],f[i-1][j - k * c[i]] + k * w[i]};/*表示前i-1种物品中选取若干件物品放入剩余空间为j-k*w[i]的背包中所能得到的最大价值加上k件第i种物品的总价值*/ else/*放不下的话*/ f[i][j]=f[i-1][j]/*继承前i-1个物品在当前空间大小时的价值*/ } } } 我们可以对其进行优化：如果有两件物品a、b满足c[a]<=c[b]且w[a]>=w[b]，则将物品b去掉，不用考虑。因为你可以用 占用体积小的物品 得到 比 占用体积大的物品还要多的价值，何乐而不为呢。其实对于完全背包，可以再优化，首先将容量大于v的物品去掉，然后排序计算出容量相同的物品中价值最高的是哪个，我们只要价值大的就可以了。
画一个v=6，c[1]=1 , w[1]=3 ; c[2]=3 , w[2]=10的表格
| i\j | j=0 | j=1 | j=2 | j=3 | j=4 | j=5 | j=6 | ||
| i=0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| i=1 | 0 | 3 | 6 | 9 | 12 | 15 | 18 | ||
| i=2 | 0 | 3 | 6 | 10 | 13 | 16 | 20 | ||
以上算法可以理解成：dp每一种物品在不同剩余容量下的最优解，他是以每1种做单位的，每一种物品可以包含若干个该物品。考虑是否在该种物品中添加一件新的该物品
我们再进行优化，改变一下dp思路
我们可以把把完全背包问题转化为01背包问题来解，第i种物品最多选V/c[i]件，于是可以把第i种物品转化为v/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。
即：将一种物品拆成多件物品。
我们现在dp每一个物品，dp出该种物品在不同剩余容量下的最优解，他是以每1个为单位的。考虑是否在当前所有物品总数中添加一件新的该物品
我们用i代表前i种物品，v代表包的最大承重，c[i]是第i种物品消耗的空间、w[i]是第i种物品的价值、f[i,j]是最大价值(从前i种物品取若干件放入有j个剩余空间的包)。
如果不放那么f[i][j]=f[i-1][j]
如果确定放，那么f[i][j]=f[i][j-c[i]+w[i]]，为什么会是f[i][j-c[i]]+w[i]？
因为我们要考虑的是在当前基础上添加一件物品i。
就是说如果你放第i种物品，并不牵扯到第i-1种物品，所以不管你放多少件，都要在第i种商品的基础上操作
所以说递推式为：
f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])
该代码：
for (int i = 1; i <= n; ++i) { for (int j = 1; j <= v; ++j) { if (c[i] <= j) f[i][j] = max(f[i - 1][j],f[i][j - c[i]] + v[i]); else f[i][j] = f[i - 1][j]; } } 我们可以继续优化此算法，可以用一维数组写
我们先回顾01背包为什么写1维要逆序？
因为为了避免要使用的子状态收到影响。
那我们该如何写完全背包的1维优化呢？
答案是：顺序
因为第i种物品一旦出现，原来没有第i种物品的情况下可能有一个最优解，现在第i种物品 出现了，而它的加入有可能得到更优解，所以之前的状态需要进行改变，故需要正序。
所以说递推式是这样子的：
f[j] = max(f[j],f[j-c[i]]+w[i])
贴出代码：
for (int i = 1; i <= n; ++i) { for (int j = w[i]; j <= v; ++j) { f[j] = max(f[j], f[j - c[i]] + v[i]); } } 如果此文写的有bug,请及时留言！谢谢
本文章原创，未经我允许不得转载
Authentic Author : Tranx
2017.10.2 19:18