多重背包(MultPack = ZeroOnePack + CompletePack)

HiHoCoder_offer6_04

题目4 : 奖券兑换

时间限制:20000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi在游乐园中获得了M张奖券，这些奖券可以用来兑换奖品。

可供兑换的奖品一共有N件。第i件奖品需要Wi张奖券才能兑换到，其价值是Pi。

小Hi使用不超过M张奖券所能兑换到的最大奖品总价值是多少？

输入

第一行两个整数N，M。

接下来N行，每行两个整数Wi，Pi。

对于 50%的数据： 1≤N,M≤1000

对于 100%的数据： 1≤N,M≤105,1≤Pi,Wi≤10。

输出

一行一个整数，表示最大的价值。

样例输入

样例输出

　　明显是一个01背包问题，背了一下结果：过了一半的数据，剩下的TLE了。仔细观察数据， 1 <= n , m <= 100000, 1 <= wi , pi <= 10。明显每个物品的价值和容量都非常小，也就是说不同容量不同不价值的物品最多有：10 * 10 = 100种。

既然这个数据项这么小，那么它就是这个问题的突破口。对于每一个物品，已知它的num(数量 )和 weight(重量) & value(价值),刚好可以使用多重背包。加上二进制优化，复杂度O(10 * 10 * log 100000);

代码：

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int num[15][15];
int dp[100005];

void CompletePack(int weight, int value, int totWeight)
{
    for(int w = weight; w <= totWeight; w ++){
        dp[w] = max(dp[w], dp[w - weight] + value);
    }
}

void zeroOnePack(int weight, int value, int totWeight)
{
    for(int w = totWeight; w >= weight; w --){
        dp[w] = max(dp[w], dp[w - weight] + value);
    }
}

void multiPack(int weight, int value, int totWeight)
{
    if(weight * num[weight][value] > totWeight){
        CompletePack(weight, value, totWeight);
    }else{
        int k = 1, tmpNum = num[weight][value];
        while(k < tmpNum){
            zeroOnePack(k * weight, k * value, totWeight);
            tmpNum -= k;
            k <<= 1;
        }
        zeroOnePack(tmpNum * weight, tmpNum * value, totWeight);
    }
}

int main()
{
    int n,m,weight,value;
    cin>>n>>m;
    for(int i = 0; i < n; i ++){
        scanf("%d%d",&weight, &value);
        num[weight][value] ++;
    }
    for(int i = 1; i <= 10; i ++){
        for(int j = 1; j <= 10; j ++){
            multiPack(i, j, m);
        }
    }
    printf("%d
",dp[m]);
    return 0;
}

————————++++++————————