首页 > 代码库 > zoj 3812 We Need Medicine (dp 状压)
zoj 3812 We Need Medicine (dp 状压)
先贴一下转载的思路和代码，，，：http://blog.csdn.net/qian99/article/details/39138329
状压dp博大精深啊，以后看到n<=50都可以往状压上想，orz
A terrible disease broke out! The disease was caused by a new type of virus, which will lead to lethal lymphoedema symptom. For convenience, it was named LL virus.
After several weeks of research, the scientists found the LL virus highly lethal and infectious. But more importantly, it has a long incubation period. Many victims were unaware of being infected until everything was too late. To prevent from the apocalypse, we need medicine!
Fortunately, after another several weeks of research, the scientists have finished the analysis of the LL virus. You need write a program to help them to produce the medicine.
The scientists provide you N kinds of chemical substances. For each substance, you can either use it exact Wi milligrams in a medicine, or not use it. Each selected substance will add Ti points of therapeutic effect value (TEV) to the medicine.
The LL virus has Q different variants. For each variant, you need design a medicine whose total weight equals to Mi milligrams and total TEV equals to Si points. Since the LL virus is spreading rapidly, you should start to solve this problem as soon as possible!
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N (1 <= N <= 400) and Q (1 <= Q <= 400).
For the next N lines, each line contains two integers Wi (1 <= Wi <= 50) and Ti (1 <= Ti <= 200000).
Then followed by Q lines, each line contains two integers Mi (1 <= Mi <= 50) and Si (1 <= Si <= 200000).
Output
For each test case, output Q lines. For the i-th line, output the indexes (1-based) of chemical substances in the i-th medicine, separated by a space. If there are multiple solutions, output any one. If there is no solution, output "No solution!" instead.
Sample Input
13 32 101 121 53 154 273 17
Sample Output
1 33 2 1No solution!
Author: JIANG, Kai Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
转自：http://blog.csdn.net/qian99/article/details/39138329
题意：给出n个物品，每个物品有两种属性Wi,Ti，有q组查询，每组查询要求在n个物品中选出一些，并使得两个属性的和为Mi，Si。
思路：刚开始看感觉是神题，后来仔细想了想，其实本质上就是个背包。最裸着写的话，那么就是dp[i][j][k]表示使用前i个物品，是否可以凑出第一个属性j，第二个属性k，要输出方案的话记录一下路径就可以了。一开始这么写了一发，加了一些乱七八糟的优化，还是会T。虽然这题时限还算宽，但这么写复杂度还是太高了。考虑到第一个属性最多只有50，那么可以用一个二进制数来表示是否能凑出第一个属性的情况，即：第i位为1表示可以凑出i。使用这种方法的好处是对于物品i可以直接算出第一种属性的组合情况，枚举一下新增的位，更新一下结果就行了。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 410 11 #define M 200010 12 #define mod 6 13 #define mod2 100000000 14 #define ll long long 15 #define ull unsigned long long 16 #define maxi(a,b) (a)>(b)? (a) : (b) 17 #define mini(a,b) (a)<(b)? (a) : (b) 18 19 using namespace std; 20 21 int T; 22 int n,q; 23 int w[N],t[N]; 24 int m,s; 25 ull f[M]; 26 int ans[M][52]; 27 map<ull,int>mt; 28 29 void ini1() 30 { 31 int i; 32 for(i=1;i<=52;i++){ 33 mt[ (1ll<<(i-1ll)) ]=i; 34 } 35 } 36 37 void ini() 38 { 39 int i,j; 40 ull k,x; 41 ull v; 42 scanf("%d%d",&n,&q); 43 memset(ans,0,sizeof(ans)); 44 memset(f,0,sizeof(f)); 45 for(i=1;i<=n;i++){ 46 scanf("%d%d",&w[i],&t[i]); 47 } 48 f[0]=1; 49 for(i=1;i<=n;i++){ 50 for(j=200000;j>=t[i];j--){ 51 v=f[j]; 52 f[j] |= (f[j-t[i]]<<w[i]) & ( (1ll<<52)-1 ); 53 for(k=v ^ f[j];k>0;k &= (k-1) ) 54 { 55 x=(k ^(k-1))&k; 56 ans[j][ mt[x]-1 ]=i; 57 } 58 } 59 } 60 } 61 62 void solve() 63 { 64 int te; 65 while(q--) 66 { 67 scanf("%d%d",&m,&s); 68 if(ans[s][m]==0){ 69 printf("No solution!\n"); 70 continue; 71 } 72 else{ 73 printf("%d",ans[s][m]); 74 te=ans[s][m]; 75 m-=w[te]; 76 s-=t[te]; 77 while(m!=0) 78 { 79 printf(" %d",ans[s][m]); 80 te=ans[s][m]; 81 m-=w[te]; 82 s-=t[te]; 83 } 84 printf("\n"); 85 } 86 } 87 } 88 89 void out() 90 { 91 //printf("%lld\n",ans); 92 //cout<<ans<<endl; 93 } 94 95 96 int main() 97 { 98 ini1(); 99 // freopen("data.in","r",stdin);100 scanf("%d",&T);101 for(int cnt=1;cnt<=T;cnt++)102 // while(T--)103 //while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)104 {105 ini();106 solve();107 //out();108 }109 110 return 0;111 }
再贴一份自己加过注释的，状压dp博大精深啊：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 410 11 #define M 200010 12 #define mod 6 13 #define mod2 100000000 14 #define ll long long 15 #define ull unsigned long long 16 #define maxi(a,b) (a)>(b)? (a) : (b) 17 #define mini(a,b) (a)<(b)? (a) : (b) 18 19 using namespace std; 20 21 int T; 22 int n,q; 23 int w[N],t[N]; 24 int m,s; 25 ull f[M]; 26 int ans[M][52]; 27 map<ull,int>mt; 28 29 void ini1() 30 { 31 int i; 32 for(i=1;i<=52;i++){ 33 mt[ (1ll<<(i-1ll)) ]=i; 34 //printf(" i=%d mt=%I64d\n",i,(1ll<<(i-1ll))); 35 } 36 } 37 38 void ini() 39 { 40 int i,j; 41 ull k,x; 42 ull v,te; 43 scanf("%d%d",&n,&q); 44 memset(ans,0,sizeof(ans)); 45 memset(f,0,sizeof(f)); 46 for(i=1;i<=n;i++){ 47 scanf("%d%d",&w[i],&t[i]); 48 } 49 f[0]=1; 50 for(i=1;i<=n;i++){ 51 //printf(" i=%d\n",i); 52 //for(j=200000;j>=t[i];j--){ 53 for(j=200000;j>=t[i];j--){ 54 v=f[j]; //j原来存的值 55 te=(f[j-t[i]]<<w[i]); 56 f[j] |= (f[j-t[i]]<<w[i]) ; //j原来存的值+转移后存的值 57 // printf(" j=%d v=%I64d f=%I64d\n",j,v,f[j]); 58 for(k=v ^ f[j];k>0;k &= (k-1) ) //k初始化为新增出来的值，然后不断将k最右边的1减掉 59 // for(k=te;k>0;k &= (k-1) ) 60 { 61 x=(k ^(k-1))&k; //取k最右边的1 62 ans[j][ mt[x]-1 ]=i; 63 // printf(" k=%I64d x=%I64d mtx-1=%d ans=%d\n",k,x,mt[x]-1,ans[j][ mt[x]-1 ]); 64 } 65 } 66 } 67 } 68 69 void solve() 70 { 71 int te; 72 while(q--) 73 { 74 scanf("%d%d",&m,&s); 75 if(ans[s][m]==0){ 76 printf("No solution!\n"); 77 continue; 78 } 79 else{ 80 printf("%d",ans[s][m]); 81 te=ans[s][m]; 82 m-=w[te]; 83 s-=t[te]; 84 while(m!=0) 85 { 86 printf(" %d",ans[s][m]); 87 te=ans[s][m]; 88 m-=w[te]; 89 s-=t[te]; 90 } 91 printf("\n"); 92 } 93 } 94 } 95 96 void out() 97 { 98 //printf("%lld\n",ans); 99 //cout<<ans<<endl;100 }101 102 103 int main()104 {105 ini1();106 // freopen("data.in","r",stdin);107 //freopen("data.out","w",stdout);108 scanf("%d",&T);109 for(int cnt=1;cnt<=T;cnt++)110 // while(T--)111 //while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)112 {113 ini();114 solve();115 //out();116 }117 118 return 0;119 }
zoj 3812 We Need Medicine (dp 状压)