hdu 1059 dp再现

/* 好久没做DP了，，背包都忘了。。菜  
背包01和完全背包 就是循环顺序相反的 背包01:逆序，表示dp[i]替换的是上一状态的
完全背包:正序，替换的是当前状态的
多重背包：如果某一件物品cost*count>sum，可以把他看成一个完全背包，反之看成01背包，01背包不可以用二进制优化
题意：6件物品，第i件物品价值为i,输入第i件物品的数量，求总价值是不是可以平分，1个物品不能分多个看。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX(a,b) (a)>(b)?a:b
int sum,a[10];
int dp[60005];
void ZeroOnePack(int cost,int weight) //01背包
{
    int i;
    for(i=sum; i>=cost; i--)
    {
        dp[i]=MAX(dp[i],dp[i-cost]+weight);
    }
}
void CompletePack(int cost,int weight) //完全背包
{
    int i;
    for(i=cost; i<=sum; i++)
    {
        dp[i]=MAX(dp[i],dp[i-cost]+weight);
    }
}
void MulPack(int cost,int weight,int count) //多重背包
{
    int i;
    if(cost*count>=sum)
    {
        CompletePack(cost,weight);
        return ;
    }
    i=1;
    while(i<count)
    {
        ZeroOnePack(i*cost,i*weight);
        count-=i;
        i<<=1;
    }
    ZeroOnePack(cost*count,weight*count);
}
int main()
{
    int i,j;
    j=1;
    while(1)
    {
        sum=0;
        for(i=1; i<=6; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i]*i;
        }
        if(!sum) break;
        printf("Collection #%d:\n",j++);
        if(sum%2)
        {
            printf("Can‘t be divided.\n\n");
        }
        else
        {
            sum/=2;
            for(i=0; i<=sum; i++)
                dp[i]=0;
            for(i=1; i<=6; i++)
            {
                if(a[i])
                    MulPack(i,i,a[i]);
            }
            if(dp[sum]==sum)
                printf("Can be divided.\n\n");
            else
                printf("Can‘t be divided.\n\n");
        }
    }
    return 0;
}

hdu 1059 dp再现,布布扣,bubuko.com

hdu 1059 dp再现

原文：http://blog.csdn.net/littlefool5201314/article/details/22613563