背包问题模板，POJ(1014)

题目链接：http://poj.org/problem?id=1014

背包问题太经典了，之前的一篇博客已经讲了背包问题的原理。

这一个题目是多重背包，但是之前的枚举是超时的，这里采用二进制优化。

这是所有01背包，完全背包，多重背包的模板哦！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int sum;
int num[7], dp[60000 + 60];

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

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

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


int main()
{
    int t = 1;
    while (~scanf("%d", &num[1]))
    {
        sum = num[1];
        for (int i = 2; i <= 6; i++)
        {
            scanf("%d", &num[i]);
            sum += num[i] * i;
        }
        if (num[1] + num[2] + num[3] + num[4] + num[5] + num[6] == 0) break;
        printf("Collection #%d:
", t++);
        if (sum % 2)
        {
            puts("Can't be divided.
");
            continue;
        }
        sum >>= 1;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= 6; i++)
        {
            MultiPack(i, i, sum, num[i]);
        }
        if (dp[sum] != sum)
        {
            puts("Can't be divided.
");
        }
        else
            puts("Can be divided.
");
    }
    return 0;
}