个人可以做几个网站,网站建设做的好,商城网站建设定制网站建设,吉林省工伤保险网站多重背包我们其实可以看成为01背包和完全背包的组合。也可以把多重背包问题只转换成01背包问题#xff0c;我们一起来看看解题思路。
1.状态表示
DP问题我们先来看状态表示,
二维数组的表示#xff0c;F[i][j]代表到 i 个物品时#xff0c;当前背包容量为 j 时所能拿到的…
多重背包我们其实可以看成为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件1kSi 然后我们就把问题看成仅有一件的占用空间k*Vi 价值为k*Wi的物品该不该拿。这么说就应该很容易理解了然后我们要做的就是在判断这个k件物品合成的 大物件该不该拿之前先枚举 k 的大小就可以了。
2小优化转化为01完全背包
前面我们是把所有物品全部转化成01背包来做但是我们想一想是不是有的物品可以转化成完全背包呢
完全背包问题是每件物品全部是无限件。我们这里有无限拿的物品吗我们可以想想总的背包体积就是 V 是已经确定了的如果我们有一种物品占用体积为 v共有 s 件但s*v V不就代表着我们连 s 件物品都不可能拿完背包就已经塞不下了吗所以这种情况我们可以转换成完全背包来做只需要加一个判断就可以了。
为什么要转换成完全背包我们看上面转化成01背包是需要枚举一下拿多少件的而转化为完全背包是不需要枚举多少件的可以拿我们就拿所以在时间上会有一些优化。
//转化为01和完全背包
#includebits/stdc.h
using namespace std;
const int MAXN101;
int n,V;
int v[MAXN],w[MAXN],s[MAXN];
int f[MAXN];
int main()
{cinnV;for(int i1;in;i)cinv[i]w[i]s[i];for(int i1;in;i){if(s[i]*v[i]V)//转化为完全背包 {for(int jv[i];jV;j)f[j]max(f[j-v[i]]w[i],f[j]);}else //转化为 01背包 {for(int jV;jv[i];j--)for(int ks[i];k0;k--)if(jk*v[i])f[j]max(f[j-k*v[i]]k*w[i],f[j]);}}coutf[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 看一眼代码
//如果没接触过可以代入s10试一下k1;cnt0;
while(ks)//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;
}
因为如果是82件的话我们如果仅仅想拿5件就无法表示了
我们把这10个单独的物品经过处理 就分成了
1件 价值w体积v的物品 1件 价值2w体积2v的物品 一件 价值3w体积3v的物品和一件 价值4w体积4v的物品
共四个新物品每个物品仅有一件这样就可以表示1-10内所有的数啦
剩下的 聪明的你看代码肯定秒懂~~~~
//二进制优化
#includebits/stdc.h
using namespace std;
const int MAXN1e510;
int n,V;
int v[MAXN],w[MAXN];
int f[MAXN];
int main()
{cinnV;int cnt0;//记录新的物体数 for(int i1,a,b,s;in;i){cinabs;int k1;while(ks)//将每个物品都按照二进制合成{v[cnt]k*a;w[cnt]k*b;s-k;k*2;}if(s){v[cnt]s*a;w[cnt]s*b;}}for(int i1;icnt;i)//01背包 for(int jV;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);coutf[V];return 0;
}
2单调队列优化
单调队列的优化是比较难想的我们的思想是对拿多少件物品分类。那么怎么分类呢设 V 为背包体积v 为第 i 种物品占用空间体积无论拿多少件这种物品最后的最后枚举完所有物品后背包剩余体积是一定小于每种物品体积的如果大于等于那么一定还可以再装这与最高价值矛盾。所以我们就根据剩余体积来给分类。
假设第 i 种物品占用体积为 v 价值为 w我们枚举装完物体后剩余体积为0,1,2,3,4,5...v-1不可能剩余v 那么就可以再装一个本种物品了。怎么枚举呢下面有代码
for(int i1,v,w,s;in;i)for(int j0;jv;j)for(int kj;kV;kv)
最外面一层循环用 i 枚举第 i 个物品j 枚举哪一组k枚举组别里面的不同个体。
f [0] f [v] f [2*v] ... f [k*v]
f [1] f [1v] f [12*v] ... f [1k*v]
f [2] f [2v] f [22*v] ... f [2k*v]
……
f [j] f [jv] f [j2*v] ... f [jk*v]
通过这种表示我们可以看出已经可以把背包容量的各个状态表示出来。
所以我们的最优解是{ f [j], f [jv], f [j2*v], f [j3*v], ... , f [jk*v] } 中的最大值也就是上述矩阵中每一行的最大值。
我们就可以把这个问题分成 j 类每一类通过一个单调队列维护就成为了 j 个单调队列的问题。
拿第 j 个单调队列来看
f [j] f [j]
f [jv] max(f [j] w ,f [jv] )
f [j2*v] max(f [j] 2*w, f [jv] w, f [j2*v])
f [j3*v] max(f [j] 3*w, f [jv] 2*w, f [j2*v] w , f[j3*v] )
……
f [jk*v] max( f [j]k*w, f[jv] (k-1)*w,..., f [jk*v] )
这样并不利于我们表示我们稍微转化一下
f [j] f [j]
f [jv] max(f [j] ,f [jv] - w) w
f [j2*v] max(f [j], f [jv] - w, f [j2*v] - 2*w) 2*w
f [j3*v] max(f [j], f [jv] - w, f [j2*v] - 2w , f [j3*v] - 3*w) 3*w
……
f [jk*v] max( f [j], f[jv] - w,..., f [jk*v] - k*w) k*w
如此看来我们每次入队列 f [jk*v] - k*w 维护其中的最大值就可以了。
看一下入队操作
int hh0,tt-1;
for(int tj;tV;tv)
{if(hhttt-s*vq[hh]) hh;while(hhttpre[q[tt]]-(q[tt]-j)/v*w pre[t]-(t-j)/v*w) tt--;if(hhtt) f[t]max(f[t],pre[q[hh]](t-q[hh])/v*w);q[tt] t;
}
q数组中保存了上述写的 当 f [jk*v] - k*w 最大时的下标入队前如果队首不在滑动窗口内队首出队每次入队元素如果比队列中元素大就弹出队尾。
pre数组记录前一类 f 数组的状态代码中我们直接用 t 表示了上述过程的 jk*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)这就是我们每次的比较值。
接下来是代码环节
//单调队列优化
#includebits/stdc.husing namespace std;
const int MAXN20010;
int n,f[MAXN],q[MAXN],pre[MAXN];
int main()
{int n,V;cinnV;for(int i1,v,w,s;in;i){cinvws;memcpy(pre,f,sizeof(f));for(int j0;jv;j)//j个单调队列 {int hh0,tt-1;for(int tj;tV;tv){if(hhttt-s*vq[hh]) hh;while(hhttpre[q[tt]]-(q[tt]-j)/v*w pre[t]-(t-j)/v*w) tt--;if(hhtt) f[t]max(f[t],pre[q[hh]](t-q[hh])/v*w);q[tt] t;}}}coutf[V];return 0;
}
