题目相同,但是时限不同,原本上面的多重背包我初始化为0,f[0] = 1;用位或进行优化,f[i]=1表示可以兑成i,0表示不能。
在poj上运行时间正好为时限3000ms....太慢了,hdu直接TLE(时限1s);
之 后发现其实并不是算法的问题,而是库函数的效率没有关注到。我是使用fill()按量初始化的,但是由于memset()可能是系统底层使用了四个字节拷 贝的函数(远比循环初始化快),效率要高得多。。这就是为什么一直TLE的原因,fill虽然可以任意赋值,但是效率实在是太低;在hdu中一个很奇怪的 现象,就是在memset中,使用memset(f,0,(V+1)*sizeof(int))也会TLE..这又是为何;但是在POJ中,无论如何,运 行时间都是3000ms...
hdu 296MS 1956K
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define inf 0x3f3f3f3f const int M = 100100; int f[M],V; int w[110],num[110]; void ZeroOnePack(int w,int c) { for(int v = V;v >= w;v--) f[v] |= f[v-w]; } void CompletePack(int w,int c) { for(int v = w;v <= V;v++) f[v] |= f[v-w]; } void MultiPack(int w,int c,int num) { if(w*num >= V) CompletePack(w,c); else{ for(int k = 1;k < num;k <<= 1){ ZeroOnePack(w*k,k*c); num -= k; } ZeroOnePack(w*num,num*c); } } int main() { int n; while(scanf("%d%d",&n,&V) == 2 && n+V){ memset(f,0,sizeof(f)); f[0] = 1; rep1(i,1,n) scanf("%d",w + i); rep1(i,1,n) scanf("%d",num + i); rep1(i,1,n){ MultiPack(w[i],w[i],num[i]); } int ans = 0; rep1(i,1,V)if(f[i]) ans++; printf("%d ",ans); } }
同样的题目 hdu 1059 dividing
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } const int M = 70001; int f[M],V; void ZeroOnePack(int w) { for(int v = V;v >= w;v--) f[v] |= f[v-w]; } void CompletePack(int w) { for(int v = w;v <= V;v++) f[v] |= f[v-w]; } void MultiPack(int w,int num) { if(w*num >= V){ CompletePack(w); } else{ for(int k = 1;k < num;k <<= 1){ ZeroOnePack(w*k); num -= k; } ZeroOnePack(w*num); } } int main() { int num[7],w[7],kase = 1; while(1){ int sum = 0; rep1(i,1,6) read1(num[i]),w[i] = i,sum += num[i]*i; if(sum == 0) break; printf("Collection #%d: ",kase++); if(sum & 1){ puts("Can't be divided. "); continue; } MS0(f); f[0] = 1; V = sum >> 1; rep1(i,1,6) MultiPack(w[i],num[i]); if(f[V]) puts("Can be divided. "); else puts("Can't be divided. "); } return 0; }