传送门：http://poj.org/problem?id=1014

 

第一次碰到多重背包

刚开始还想一言不合就dfs但是会超时啊……看了别人的才知道是多重背包

http://blog.csdn.net/zxy_snow/article/details/6169008

http://blog.csdn.net/zcube/article/details/48223063

主要是看了这两个

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 int con,sum; 6 int marble[300010]; 7 int bag[300010]; 8 int a,b,c,d,e,f; 9 int num;10 int k;11 12 void split(int x,int n){13     int temp=0;14     int m;15     for(int i=0; ;i++){16         m=1<
       
        x){18             break;19         }20         marble[num++]=m*n;21         temp+=m;22     }23     if(x-temp>0){24         marble[num++]=(x-temp)*n;25     }26 }27 28 bool dp(){29     for(int i=0;i
        
         =marble[i];j--){31             if((bag[j-marble[i]]+marble[i])>bag[j]){32                 bag[j]=bag[j-marble[i]]+marble[i];33             }34         }35     }36     return bag[sum]==sum;37 }38 39 int main(){40     k=0;41     while(cin>>a>>b>>c>>d>>e>>f){42         if(!(a||b||c||d||e||f)){43             break;44         }45         k++;46         cout<<"Collection #"<
         
          <<":"<