好贷网好贷款

poj 1742 多重背包变种 对时间要求特别严格

发布时间:2016-12-5 10:31:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1742 多重背包变种 对时间要求特别严格",主要涉及到poj 1742 多重背包变种 对时间要求特别严格方面的内容,对于poj 1742 多重背包变种 对时间要求特别严格感兴趣的同学可以参考一下。

1 多重背包物品二进制拆分后01背包#include <iostream> #include <stdio.h> #include <cstring> using namespace std; #define MAX_V (100+1) #define MAX_F (100000+1) int A[MAX_V],C[MAX_V]; int Value[MAX_F]; bool F[MAX_F]; int n,m; #define printf // int main() { while(scanf("%d %d",&n,&m) != EOF) { if(n==0 && m== 0) return 0; for(int i=1;i<=n;i++) { scanf("%d",&A[i]); //cin>>A[i]; } for(int i=1;i<=n;i++) { scanf("%d",&C[i]); //cin>>C[i]; } int cnt = 0; //binary拆分物品 //C数量 A价值 for(int i=1;i<=n;i++) { printf("old:数量:%d 价值:%d\n",C[i],A[i]); int tc = C[i]; for(int k=1;k<=tc; k <<= 1) { Value[cnt++] = A[i] *k; tc -= k; printf("\t\t %d:价值:%d \n",k,k*A[i]); } if(tc > 0) { Value[cnt++] = A[i] * tc; printf("\t\t%d:价值:%d\n",C[i],C[i]*A[i]); } } memset(F,0,sizeof(F)); F[0]=true; for(int i=0;i<cnt;i++) { //for(int v=m;v>Value[i];v--) for(int v=m;v>=Value[i];v--) { if(F[v]) continue; if(F[v-Value[i]]) F[v] = true; //F[v] = F[v] || F[v-Value[i]]; printf("i=%d(%d) F[v-x]=%d F[%d]=%d\n",i,Value[i],F[v-Value[i]],v,F[v]); // if(F[v - Value[i] ] + value[i] > F[v]) // F[v] = F[v - value[i] ] + value[i]; } } int sums = 0; for(int v=m;v>0;v--) if(F[v]) { ++sums; } cout<<sums<<endl; } } 2 按照之前网上说的思路尝试优化,但依然不理想,依然TLE.#include <iostream> #include <stdio.h> #include <cstring> using namespace std; #define MAX_V (100+1) #define MAX_F (100000+1) int A[MAX_V],C[MAX_V]; int Value[MAX_F]; bool F[MAX_F]; //F[v]为使用i能否达到v int n,m; #define printf // int main() { while(scanf("%d %d",&n,&m) != EOF) { if(n==0 && m== 0) return 0; for(int i=1;i<=n;i++) { scanf("%d",&A[i]); //cin>>A[i]; } for(int i=1;i<=n;i++) { scanf("%d",&C[i]); //cin>>C[i]; } memset(F,0,sizeof(F)); F[0]=true; int maxv = 0; int sum = 0; for(int i=1;i<=n;i++) { for(int v=maxv;v>=0;v--) { if(F[v]) { for(int k=1;k<= C[i];k++) { int ki = v+ k*A[i]; if(ki >m ) break; if(F[ki]) continue; ++sum; F[ki]= true; if(ki > maxv) maxv = ki; } } } } // int sums = 0; // for(int v=m;v>0;v--) // { // printf("%d=%d\n",v,F[v]); // if(F[v]) // { // ++sums; // } // } cout<<sum<<endl; } } 3 参考 http://blog.csdn.net/qingniaofy/article/details/7882407 混合 完全背包和01背包优化解决多重背包问题 如果一个物品的value*amount >= m时,则认为此物品可以取任意多件,因为在物品的件数限制amount内,一定可以满足m了。 #include <iostream> #include <stdio.h> #include <cstring> using namespace std; #define MAX_V (100+1) #define MAX_F (100000+1) int A[MAX_V],C[MAX_V]; bool F[MAX_F]; int n,m; #define printf // void ZeroOnePack(int value) { printf("zero one pack value:%d\n",value); for(int v=m;v>=value;--v) { F[v] |= F[v-value]; printf("F[%d] = %d\n",v,F[v]); } } void CompletePack(int value) { for(int v=value;v<=m;v++) //完全背包和01背包只有循环顺序不同,具体可参考背包问题九讲 F[v] |= F[v-value]; } void MultiPack(int value,int amount) { if(value * amount >= m) { CompletePack(value); return; } //这段对某些可以应用完全背包的物品,进行完全背包才最终AC的。 int k=1; while(k<amount) { ZeroOnePack(value * k); amount -= k; k <<= 1; } if(amount) ZeroOnePack(value*amount); } int main() { while(scanf("%d %d",&n,&m) != EOF) { if(n==0 && m== 0) return 0; for(int i=1;i<=n;i++) { scanf("%d",&A[i]); } for(int i=1;i<=n;i++) { scanf("%d",&C[i]); } memset(F,0,sizeof(F)); F[0] = true; //数量c for(int i=1;i<=n;i++) { if(C[i]) { MultiPack(A[i],C[i]); } } int sums = 0; for(int v=m;v>0;v--) if(F[v]) { ++sums; } cout<<sums<<endl; } }

上一篇:素数表
下一篇:SQL2005CLR函数扩展-字符串函数

相关文章

相关评论