小说网站 做百度联盟,网站建设中模板,如何做一个网站设计,知名品牌文章目录 一、多重背包问题特点1.1、多重背包问题的特征1.2、解决多重背包问题的基本方法典型例题#xff1a;AcWing——多重背包问题I 1.3、二进制优化1.3.1、二进制优化的思想1.3.2、多重背包问题的二进制优化 一、多重背包问题特点
多重背包问题是背包问题的又一变种… 文章目录 一、多重背包问题特点1.1、多重背包问题的特征1.2、解决多重背包问题的基本方法典型例题AcWing——多重背包问题I 1.3、二进制优化1.3.1、二进制优化的思想1.3.2、多重背包问题的二进制优化 一、多重背包问题特点
多重背包问题是背包问题的又一变种它在0-1背包和完全背包问题的基础上增加了一个限制每种物品i除了有一个重量w[i]和价值v[i]外还有一个最大可用数量n[i]。这意味着每种物品i可以被选取的次数最多是n[i]次而不是只有一次0-1背包问题或无限次完全背包问题。
1.1、多重背包问题的特征
有限的物品数量每种物品有一个最大数量限制不能无限制地选择。背包容量限制存在一个容量限制所有选取的物品的总重量不能超过这个限制。优化目标目标是在不超过背包容量的前提下最大化背包内物品的总价值。复杂度时间和空间复杂度取决于具体的实现方法一般时间复杂度为O(V*sum(n[i]))。
1.2、解决多重背包问题的基本方法
解决多重背包问题的基本思路是利用动态规划其中最直观的方法是使用二维DP数组dp[i][j]表示考虑前i种物品在不超过重量j的情况下的最大价值。和0-1背包问题的区别在于物品i能取n[i]次因此状态转移方程可以写为
for(int k0;kn[i];k)if(j-k*weight[i]0)dp[i][j]max(dp[i][j],dp[i-1][j-k*weight[i]]k*value[i]);这里k是从0到n[i]的整数表示选择第i种物品k次的可能性。
由于这种方法会导致较高的时间复杂度时间复杂度为O(V*sum(n[i]))特别是当n[i]的值很大时常常需要使用其他技巧。
典型例题AcWing——多重背包问题I
AcWing多重背包问题I 按照以上思路并且按照0-1背包一样的思路进行降维优化。 for(int i0;iN;i)for(int jV;jvolume[i];--j)for(int k0;kn[i];k)if(j-k*volume[i]0)dp[j]max(dp[j],dp[j-k*volume[i]]k*value[i]);本题可以书写代码为
#includebits/stdc.h
using namespace std;
int dp[101];
int main(void){ios_base::sync_with_stdio(false);cin.tie(0);int N,V;cinNV;vectorint volume(N);vectorint value(N);vectorint n(N);for(int i0;iN;i){cinvolume[i]value[i]n[i];}for(int i0;iN;i)for(int jV;jvolume[i];--j)for(int k0;kn[i];k)if(j-k*volume[i]0)dp[j]max(dp[j],dp[j-k*volume[i]]k*value[i]);coutdp[V];return 0;
}1.3、二进制优化
1.3.1、二进制优化的思想
对于任何一个数我们可以将其进行二进制拆分。即任何一个10进制数都能写成二进制数的形式。 比如31211B、10281010B。
如果我们对于一个数例如10取出小于其的所有二进制位即1B,10B,100B,1000B那么我们必然能够选出其中的某些位来凑成10并且对于小于10的任何一个正整数也可以被凑成即选取其中若干位有1B、10B、11B、100B、101B、110B、111B、1000B、1001B···。即如果我们有一个物品它能够被选择小于等于n次我们可以通过选择其中的某些位来实现选择的所有情况。
那么我们把一个物品可以最多选择n次的问题按照未优化的多重背包问题需要进行O(V*sum(n[i]))次计算取最大值 变成了 考虑在logn个物品中选择其中的某些物品取最大值 的问题了。按到理来说logn个物品要么被选要么不被选一共是2的logn次方种情况也就是n种情况但是如果我们把这个问题转化成0-1背包问题即利用动态规划来考虑就变成了O(V*sum(logn[i]))次了。当n[i]2000时,logn[i]3.301减少了一千倍计算量。
因此我们对于n[i]可以进行二进制拆分将n[i]个物品按照二进制拆分变成若干堆每次选择只能一次全选这样使得我们需要考虑的物品变成logn[i]个多重背包问题变成了一个0-1背包问题即这logn[i]个物品要么被选要么不被选能够取得的最大值。我们通过上述叙述可以知道logn[i]个物品的所有被选择的情况刚好构成了0~n[i]中的所有数字。
由于一个物品的数量n不一定是2的整数倍因此我们在考虑二进制的时候因为我们的目的是凑成0~ n因此我们在考虑二进制的时候我们考虑到小于等于n/2位即可它们能满足0~ k种情况kn/2然后剩余的n-k部分直接单独成一块就行这样能满足n-k~ kn-k种情况合并起来就是0~n中情况。
1.3.2、多重背包问题的二进制优化
通过二进制拆分我们将m个物品每个最多选n[i]次的多重背包问题转换成了 sum(logn[i])个物品的0-1背包问题。相当于进行了问题转换。
代码
#includebits/stdc.h
using namespace std;
int dp[2002];
int main(void){ios_base::sync_with_stdio(false);cin.tie(0);int N,V;cinNV;vectorint value;vectorint volume;for(int i0;iN;i){//构建二进制拆分物品int w,v,num;cinwvnum;//w单物品体积v单物品价值num可选数量int snum;int b1;while(bs){//注意b必须是小于num且不能是最高位 如1010Bb不能是1000Bvalue.push_back(b*v);volume.push_back(b*w);s-b;b*2;}if(s0){value.push_back(s*v);volume.push_back(s*w);}}Nvalue.size();//更新物品数量for(int i0;iN;i)for(int jV;jvolume[i];--j)dp[j]max(dp[j],dp[j-volume[i]]value[i]);coutdp[V];return 0;
}位数关系即 int snum;int b1;numlog2(num);numpow(2,num-1);while(bnum){value.push_back(b*v);volume.push_back(b*w);s-b;b*2;}if(s0){value.push_back(s*v);volume.push_back(s*w);}int snum;int b1;numnum1;while(bnum){value.push_back(b*v);volume.push_back(b*w);s-b;b*2;}if(s0){value.push_back(s*v);volume.push_back(s*w);}官方
#includeiostream
using namespace std;const int N 12010, M 2010;int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积Mint main()
{cin n m;int cnt 0; //分组的组别for(int i 1;i n;i ){int a,b,s;cin a b s;int k 1; // 组别里面的个数while(ks){cnt ; //组别先增加v[cnt] a * k ; //整体体积w[cnt] b * k; // 整体价值s - k; // s要减小k * 2; // 组别里的个数增加}//剩余的一组if(s0){cnt ;v[cnt] a*s; w[cnt] b*s;}}n cnt ; //枚举次数正式由个数变成组别数//01背包一维优化for(int i 1;i n ;i )for(int j m ;j v[i];j --)f[j] max(f[j],f[j-v[i]] w[i]);cout f[m] endl;return 0;
}
