hdu1059 Dividing ——多重背包

link:http://acm.hdu.edu.cn/showproblem.php?pid=1059 最简单的那种

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
int V,m[6],c[6],w[6],f[66666];
void zeropack(int c, int w)
{
    for (int v=V;v>=c;--v) f[v]=max(f[v],f[v-c]+w);
    return;
}
void completepack(int c,int w)
{
    for(int v=c;v<=V;++v) f[v]=max(f[v],f[v-c]+w);
    return;
}
void multipack(int c,int w,int m)
{
    if(c*m>=V)
    {
        completepack(c,w); return;
    }
    int k=1;
    while (k<m)
    {
        zeropack(k*c,k*w); m-=k; k*=2;
    }
    zeropack(c*m,w*m);
    return;
}
int main(void)
{
    ios::sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int t=1; for(int i=0;i<6;++i) c[i]=w[i]=i+1;
    while (1)
    {
        int sum=0;
        for(int i=0;i<6;++i) cin>>m[i], sum+=m[i]*(i+1);
        if(!sum) break;
//        if(t!=1) cout<<endl;
        cout<< "Collection #"<<t<<":\n";
        t++;
        if(sum&1) {cout<< "Can't be divided."<<endl<<endl; continue;}
        V=sum/2;
        memset(f,-INF,sizeof(f)); f[0]=0;
        for(int i=0;i<6;++i) multipack(c[i],w[i],m[i]);
        if(f[V]<0) cout<< "Can't be divided."<<endl;
        else cout<< "Can be divided."<<endl;
        cout<<endl;
    }
    return 0;
}

其实还是要理解一下这个思想……不能单靠记忆