首页 > 代码库 > 多重背包转换成完全背包和01背包

多重背包转换成完全背包和01背包

void CompletePack(int cost,int weight)   多重背包
{  
    for(int i=cost;i<=m;i++)  
    dp[i]=max(dp[i],dp[i-cost]+weight);  
}  
void ZeroOnePack(int cost,int weight)    01背包
{  
    for(int i=m;i>=cost;i--)  
    dp[i]=max(dp[i],dp[i-cost]+weight);  
}  
void MultiplyPack(int cost,int weight,int amount)   完全背包
{  
    if(cost*amount>=m)  
    CompletePack(cost,weight);  
    else  
    {  
    int k=1;  
    while(k<amount)  
    {  
        ZeroOnePack(k*cost,k*weight);  
        amount-=k;  
        k<<=1;  
    }  
    ZeroOnePack(amount*cost,amount*weight);  
    }  


详情看
HDU 2844 Coins (动规)