网站关键词分隔网络营销的优势有哪些
多重背包我们其实可以看成为01背包和完全背包的组合。也可以把多重背包问题只转换成01背包问题，我们一起来看看解题思路。
1.状态表示
DP问题我们先来看状态表示,
二维数组的表示，F[i][j]代表到 i 个物品时，当前背包容量为 j 时所能拿到的最大价值。非常容易理解，我们主要考虑一下优化，用一维数组来表示，则用 F [j] 代表当前背包容量为 j时所能拿到的最大价值。第i个物体的体积为v[i]，价值为 w [i]。
然后我们就看如何把多重背包转换成01背包与完全背包。
当然，01背包和完全背包转移方程都是
F [j]=max(F [j], F [ j- v [i] ]+ w [i])
2.转换
（1）转换为01背包
我们知道，01背包问题指的是各个物品只有一件，但在多重背包问题中，我们每种物品有 Si 件。
我们可以考虑将多个同种物品合成一件物品。比如，我们有10件t恤，一件占空间2，每件价值20元，我们将8件t恤合在一起，就变成了一件1占空间为16的价值160元的t恤。如此一来，多重背包问题就被我们转换为01背包问题啦。
换一种更为简单的说法，我们本身的问题就是不知道一种占用空间 Vi ，价值为 Wi，数量为 Si 的物品该拿多少件，我们就把该拿多少件枚举一下，假设为 k件（1<=k<=Si） ，然后我们就把问题看成仅有一件的占用空间k*Vi ，价值为k*Wi的物品该不该拿。这么说就应该很容易理解了，然后我们要做的就是，在判断这个k件物品合成的 大物件该不该拿之前，先枚举 k 的大小就可以了。
（2）小优化，转化为01+完全背包
前面我们是把所有物品全部转化成01背包来做，但是我们想一想，是不是有的物品可以转化成完全背包呢？
完全背包问题是每件物品全部是无限件。我们这里有无限拿的物品吗？我们可以想想，总的背包体积就是 V ，是已经确定了的，如果我们有一种物品占用体积为 v，共有 s 件，但s*v >=V，不就代表着我们连 s 件物品都不可能拿完背包就已经塞不下了吗？所以这种情况我们可以转换成完全背包来做，只需要加一个判断就可以了。
为什么要转换成完全背包？我们看上面转化成01背包是需要枚举一下拿多少件的，而转化为完全背包是不需要枚举多少件的，可以拿我们就拿，所以在时间上会有一些优化。
//转化为01和完全背包
#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
int n,V;
int v[MAXN],w[MAXN],s[MAXN];
int f[MAXN];
int main()
{cin>>n>>V;for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];for(int i=1;i<=n;i++){if(s[i]*v[i]>=V)//转化为完全背包 {for(int j=v[i];j<=V;j++)f[j]=max(f[j-v[i]]+w[i],f[j]);}else //转化为 01背包 {for(int j=V;j>=v[i];j--)for(int k=s[i];k>=0;k--)if(j>=k*v[i])f[j]=max(f[j-k*v[i]]+k*w[i],f[j]);}}cout<<f[V];return 0;
}3.优化
（1）二进制优化
我们想如果我想要拿512件物品，按照转化成01背包的方法做，我们是需要从拿1件枚举到拿512件的，而二进制优化也就带了那么点倍增思想，我们把拿多少件物品分为拿1 2 4 8 16 ... 256 512 ... 2^n 件，我们枚举的时候就枚举9次 就到了512件了。还有无论是多少件，我们总能用一些数的组合来表示，比如7 就可以用 1 + 2 + 4来表示，只需要枚举3次。这就是我们二进制优化的思想。
举一个简单的例子，一看你们肯定就明白了
第 i 种物品 我们有 10 个 ，占用空间 v，价值为 w
那么我们用二进制怎么表示这个10呢 10 = 1 + 2 + 4 + 3。为什么这么表示？而不是 8 + 2 ？看一眼代码
//如果没接触过可以代入s=10试一下k=1;cnt=0;
while(k<=s)//k为枚举个数，s为物品总件数
{v[++cnt]=k*a;w[cnt]=k*b;s-=k; //总物品数减去合成数k*=2; //k倍增
}
if(s)//如果s有剩余，将剩余件数合成为新个体
{v[++cnt]=s*a;w[cnt]=s*b;
}因为如果是8+2件的话，我们如果仅仅想拿5件，就无法表示了
我们把这10个单独的物品，经过处理 就分成了
1件 价值w体积v的物品 1件 价值2w体积2v的物品 一件 价值3w体积3v的物品和一件 价值4w体积4v的物品
共四个新物品，每个物品仅有一件，这样就可以表示1-10内所有的数啦
剩下的 聪明的你看代码肯定秒懂~~~~
//二进制优化
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,V;
int v[MAXN],w[MAXN];
int f[MAXN];
int main()
{cin>>n>>V;int cnt=0;//记录新的物体数 for(int i=1,a,b,s;i<=n;i++){cin>>a>>b>>s;int k=1;while(k<=s)//将每个物品都按照二进制合成{v[++cnt]=k*a;w[cnt]=k*b;s-=k;k*=2;}if(s){v[++cnt]=s*a;w[cnt]=s*b;}}for(int i=1;i<=cnt;i++)//01背包 for(int j=V;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);cout<<f[V];return 0;
}（2）单调队列优化
单调队列的优化是比较难想的，我们的思想是对拿多少件物品分类。那么怎么分类呢？设 V 为背包体积，v 为第 i 种物品占用空间体积，无论拿多少件这种物品，最后的最后，枚举完所有物品后背包剩余体积是一定小于每种物品体积的，如果大于等于，那么一定还可以再装，这与最高价值矛盾。所以我们就根据剩余体积来给分类。
假设第 i 种物品占用体积为 v ，价值为 w，我们枚举装完物体后剩余体积为0,1,2,3,4,5...，v-1；不可能剩余v 那么就可以再装一个本种物品了。怎么枚举呢？下面有代码
for(int i=1,v,w,s;i<=n;i++)for(int j=0;j<v;j++)for(int k=j;k<=V;k+=v)最外面一层循环用 i 枚举第 i 个物品，j 枚举哪一组，k枚举组别里面的不同个体。
f [0] f [v] f [2*v] ... f [k*v]
f [1] f [1+v] f [1+2*v] ... f [1+k*v]
f [2] f [2+v] f [2+2*v] ... f [2+k*v]
……
f [j] f [j+v] f [j+2*v] ... f [j+k*v]
通过这种表示，我们可以看出已经可以把背包容量的各个状态表示出来。
所以我们的最优解是{ f [j], f [j+v], f [j+2*v], f [j+3*v], ... , f [j+k*v] } 中的最大值，也就是上述矩阵中每一行的最大值。
我们就可以把这个问题分成 j 类，每一类通过一个单调队列维护，就成为了 j 个单调队列的问题。
拿第 j 个单调队列来看：
f [j] = f [j]
f [j+v] = max(f [j] + w ,f [j+v] )
f [j+2*v] = max(f [j]+ 2*w, f [j+v] + w, f [j+2*v])
f [j+3*v] = max(f [j]+ 3*w, f [j+v] +2*w, f [j+2*v] + w , f[j+3*v] )
……
f [j+k*v] = max( f [j]+k*w, f[j+v] + (k-1)*w,..., f [j+k*v] )
这样并不利于我们表示，我们稍微转化一下
f [j] = f [j]
f [j+v] = max(f [j] ,f [j+v] - w) + w
f [j+2*v] = max(f [j], f [j+v] - w, f [j+2*v] - 2*w) + 2*w
f [j+3*v] = max(f [j], f [j+v] - w, f [j+2*v] - 2w , f [j+3*v] - 3*w) +3*w
……
f [j+k*v] = max( f [j], f[j+v] - w,..., f [j+k*v] - k*w) + k*w
如此看来，我们每次入队列 f [j+k*v] - k*w ，维护其中的最大值就可以了。
看一下入队操作
int hh=0,tt=-1;
for(int t=j;t<=V;t+=v)
{if(hh<=tt&&t-s*v>q[hh]) hh++;while(hh<=tt&&pre[q[tt]]-(q[tt]-j)/v*w <= pre[t]-(t-j)/v*w) tt--;if(hh<=tt) f[t]=max(f[t],pre[q[hh]]+(t-q[hh])/v*w);q[++tt] = t;
}q数组中保存了上述写的 当 f [j+k*v] - k*w 最大时的下标，入队前如果队首不在滑动窗口内，队首出队，每次入队元素如果比队列中元素大，就弹出队尾。
pre数组记录前一类 f 数组的状态，代码中我们直接用 t 表示了上述过程的 j+k*v。
所以知道到底k是多少，需要用 ( t - j )/v 得出。
用 ( t - j )/v 替换 k 得到下式：
f [t] =max(f [t], pre[(maxt)] -(maxt-j)*w + (t-j)*w)
即 f [t] =max(f [t], pre[(maxt)] +(t-maxt)*w)，这就是我们每次的比较值。
接下来是代码环节：
//单调队列优化
#include<bits/stdc++.h>using namespace std;
const int MAXN=20010;
int n,f[MAXN],q[MAXN],pre[MAXN];
int main()
{int n,V;cin>>n>>V;for(int i=1,v,w,s;i<=n;i++){cin>>v>>w>>s;memcpy(pre,f,sizeof(f));for(int j=0;j<v;j++)//j个单调队列 {int hh=0,tt=-1;for(int t=j;t<=V;t+=v){if(hh<=tt&&t-s*v>q[hh]) hh++;while(hh<=tt&&pre[q[tt]]-(q[tt]-j)/v*w <= pre[t]-(t-j)/v*w) tt--;if(hh<=tt) f[t]=max(f[t],pre[q[hh]]+(t-q[hh])/v*w);q[++tt] = t;}}}cout<<f[V];return 0;
}