多重背包见 http://www.cgang.tk/pack/P03.html

mac下还是用macvim更顺手一些

在家，混混度日

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int v[7];
int sum,V;
int f[100000];

void CompletePack(int cost,int weight)
{
    for(int i=cost;i<=V;i++)
        f[i]=max(f[i],f[i-cost]+weight);
}

void ZeroOnePack(int cost,int weight)
{
    for(int i=V;i>=cost;i--)
        f[i]=max(f[i],f[i-cost]+weight);
}

void MultiplePack(int cost,int weight,int amount)
{
    if(cost*amount>=V)
    {
        CompletePack(cost,weight);
        return;
    }
    int k=1;
    while(k<amount)
    {
        ZeroOnePack(k*cost,k*weight);
        amount-=k;
        k*=2;
    }
    ZeroOnePack(amount*cost,amount*weight);
}


int main () 
{
    //freopen("in.txt","r",stdin);
    int cas=1;
    while(1)
    {
        sum=0;
        for(int i=1;i<=6;i++)
        {
            cin>>v[i];
            //v[i]=v[i]%60;
            sum+=i*v[i];
        }
        if(sum==0) break;
        cout<<"Collection #"<<cas++<<":"<<endl;

        if(sum%2)
        {
            cout<<"Can't be divided."<<endl<<endl;
            continue;
        }

        V=sum/2;
        memset(f,0,sizeof(f));
        for(int i=1;i<=6;i++)
        {
            MultiplePack(i,i,v[i]);
        }

        if(f[V]==V)
            cout<<"Can be divided."<<endl<<endl;
        else
            cout<<"Can't be divided."<<endl<<endl;
    }

}

14/10/10:背包又忘得差不多了...

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int V;
int f[100000];

void CompletePack(int cost,int weight)
{
    for(int i=cost;i<=V;i++)
        f[i]=max(f[i],f[i-cost]+weight);
}

void ZeroOnePack(int cost,int weight)
{
    for(int i=V;i>=cost;i--)
        f[i]=max(f[i],f[i-cost]+weight);
}

void MultiplePack(int cost,int weight,int amount)
{
    if(cost*amount>=V)
    {
        CompletePack(cost,weight);
        return;
    }
    int k=1;
    while(k<amount)
    {
        ZeroOnePack(k*cost,k*weight);
        amount-=k;
        k*=2;
    }
    ZeroOnePack(amount*cost,amount*weight);
}


int main ()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int cash,N,n[11],d[11];
    while(scanf("%d%d",&cash,&N)!=EOF)
    {
        for(int i=1;i<=N;i++)
            scanf("%d%d",&n[i],&d[i]);
        V=cash;
        memset(f,0,sizeof(f));
        for(int i=1;i<=N;i++)
            MultiplePack(d[i],d[i],n[i]);
        printf("%d\n",f[V]);
    }
}