poj1276——dp，多重背包

#include
#include
#include
#include
#include

using namespace std;

const int maxn=1000100;
int cash,N;
int n[maxn],D[maxn];
int dp[maxn];

void ZeroOnePack(int weight,int val)
{
    for(int i=cash;i>=weight;i--){
        dp[i]=max(dp[i],dp[i-weight]+val);
    }
}

void CompletePack(int weight,int val)
{
    for(int i=weight;i<=cash;i++){
        dp[i]=max(dp[i],dp[i-weight]+val);
    }
}

void MultiPack(int weight,int val,int amount)
{
    if(weight*amount>=cash) CompletePack(weight,val);//如果超过限制，当完全背包处理
    else{                //否则用二进制优化并转为01背包处理
        int k=1;
        while(k//按k=1,2,4,...的顺序分解amount，对分解后的部分按01背包处理
            ZeroOnePack(k*weight,k*val);
            amount-=k;
            k*=2;
        }
        ZeroOnePack(amount*weight,amount*val); //剩下部分也按01背包处理
    }
}

int main()
{
    while(cin>>cash>>N){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=N;i++){
            cin>>n[i]>>D[i];
            MultiPack(D[i],D[i],n[i]);
        }
        cout<endl;
    }
    return 0;
}