poj 1837(blance)

该题为一道简单的01背包，本题解用滚动队列（叫栈也可）稍微进行了些优化，由于该背包出现了负数，我们用10000作为表示平衡点

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 int l[22],w[22],q[2][20002],b[2][20002];
 6 int main()
 7 {
 8     int c,g;
 9     while(scanf("%d%d",&c,&g)!=EOF)
10     {
11         for(int i=0;i<c;i++)
12         scanf("%d",&l[i]);
13         for(int i=0;i<g;i++)
14         scanf("%d",&w[i]);
15         int top=0,i0=0;
16         for(int i=0;i<g;i++)
17         {
18             int rear,tail;
19             rear=tail=0;
20             if(i==0){top=1;q[i0][0]=10000;b[1-i0][0]=1;}
21             memset(b[i0],0,sizeof(b[i0]));
22             while(rear<top)
23             {
24                 int u=q[i0][rear++];
25                 for(int j=0;j<c;j++)
26                 {
27                     int v=u+l[j]*w[i];
28                     if(!b[i0][v])q[1-i0][tail++]=v;
29                     b[i0][v]+=b[1-i0][u];
30                 }
31             }
32             top=tail;
33             i0=1-i0;
34         }
35         printf("%d\n",b[1-i0][10000]);
36     }
37     return 0;
38 }