如何做网站ppt,wordpress网页怎么上传到服务器错误,免费ppt模板下载大全网站,山东大连乘法原理
百度百科
乘法原理是说把多个步骤的所有方法相乘#xff0c;表示整个事件所有可能的解决方法
原题
有 N#xfffd; 种物品和一个容量是 V#xfffd; 的背包。
第 i#xfffd; 种物品最多有 si#xfffd;#xfffd; 件#xff0c;每件体积是 vi#…乘法原理
百度百科
乘法原理是说把多个步骤的所有方法相乘表示整个事件所有可能的解决方法
原题
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si,,用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N≤10000≤1000 0V≤20000≤2000 0vi,wi,si≤20000,,≤2000
提示
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10难度中等时/空限制1s / 64MB总通过数75903总尝试数164479来源背包九讲 , 模板题算法标签 挑战模式
原题链接
传送门
代码
#includebits/stdc.h
using namespace std;const int N1100010,M200010;
int v[N],w[N];
int f[M];int main()
{int n,m;scanf(%d%d,n,m);int cnt0;for(int i0;in;i){int a,b,s;scanf(%d%d%d,a,b,s);int k1;while(ks){cnt;v[cnt]k*a;w[cnt]k*b;s-k,k*2;}if(s0){cnt;v[cnt]s*a;w[cnt]s*b;}}ncnt;for(int i1;in;i){for(int jm;jv[i];j--){f[j]max(f[j],f[j-v[i]]w[i]);}}printf(%d\n,f[m]);return 0;
}
总结
一、二进制优化 1.不优化的情况的时间复杂度是N^3在数据范围比较大的时候会超时所以我们选择二进制优化把一维的N优化为logN时间复杂度变为N^2*logN可以通过这道题
2.思路是给定了物品数目s,可以选择0件1件2件……s件物品一个一个循环的话需要循环s1次才能表示所有的情况如果我们使用二进制的话int范围内都只需要32位数字就可以表示所有数字数据范围是2000只需要最多11个数字2^1120482^0,2^1,2^2,...2^11,二进制表示本质和01背包就很相似每一个数位选择0或者是1从而可以表示所有数字
3.注意一个一般化的情况物品的件数s不是2的整数次幂比如数字102^01,2^12,2^24,2^38,0124810,如果选择到数字2^38超过了我们最多可以选择的件数10这会造成理论上可以选择多件物品但是实际上只有10件物品可以选择所以我们只能选择到2^24,01247,再补充一个数字10-73,原来的0124可以表示0~7范围的所有数字加上数字3之后可以表示0~10范围的所有数字0124表示0~7范围内所有数字的方法就是二进制计数每一个数位是否选择该数字
- - - -000 0 0
- - - - 001 1 1
- - - -010 2 2
- - - -011 3 12
- - - -100 4 4
- - - -101 5 41
- - - - 110 6 42
- - - - 111 7 421
二、代码细节
1.表示物品的数组的容量是 1000*11二进制优化表示答案的数组的容量是2000都增加10防止数组越界
2.本质是把一件物品拆成多组物品是否选择该组物品从而把多重背包转换成01背包来进行求解
3.用一个计数器来存数组下标和单链表的dix类似while循环之后加一个if特判表示最后一种情况和质因数分解类似也是判断最后处理的结果
4.原来的n件物品变成了现在的cnt件物品因为计数器从1开始作为数下标存储物品的体积和价值所以套用01背包模板的时候要从1开始遍历01背包模板的第二层循环体积从大到小遍历
