HDU-2191 买大米（动态规划多重背包）¶

Problem Description¶

急！灾区的食物依然短缺！为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮食呢？

后记：人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活—— 感谢父母，他们给予我们生命，抚养我们成人；感谢老师，他们授给我们知识，教我们做人感谢朋友，他们让我们感受到世界的温暖；感谢对手，他们令我们不断进取、努力。同样，我们也要感谢痛苦与艰辛带给我们的财富～

Input¶

输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

Output¶

对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

Sample Input¶

Sample Output¶

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int money, riceType;
vector<int> d(101, 0);
vector<int> price(101), weight(201), num(101);

void zeroOnePack(int price, int weight)
{
    for (int i = money; i >= price; --i)
        d[i] = max(d[i], d[i - price] + weight);
}

void completePack(int price, int weight)
{
    for (int i = price; i <= money; ++i)
        d[i] = max(d[i], d[i - price] + weight);
}

void multipack(int price, int weight, int num)
{
    if (price * num >= money){
        completePack(price, weight);
        return;
    } 

    int k = 1;
    while (k < num){
        zeroOnePack(k * price, k * weight);
        num -= k;
        k *= 2;
    }
    zeroOnePack(num * price, num * weight);
}

int main()
{
    int caseNum;
    cin >> caseNum;

    while (caseNum--){
        cin >> money >> riceType;

        for (int i = 1; i <= riceType; ++i){
            cin >> price[i] >> weight[i] >> num[i];
        }

        for (int i = 1; i <= riceType; ++i)
            multipack(price[i], weight[i], num[i]);

        cout << d[money] << endl;

        if (caseNum != 0) fill(d.begin(), d.end(), 0);
    }

    return 0;
}

我们令dp[i][j]==x表示只购买前i种大米, 且总费用<=j时能购买的大米最大重量为x.

初始化: dp为全0.

由于每种大米有数量num[i], 所以我们分下面两种情况做:

当cost[i]*num[i]>=n时, 我们直接对该种大米做一次完全背包过程即可.

当 cost[i]*num[i]<n时, 最直接的想法是每次多放进去去一个，然后比较所有情况： $$ f[i][j]=\max {f[i-1][j-k * w[i]]+k * v[i], 0 \leq k \leq c[i], 0 \leq k * w[i] \leq j} $$ 一个简单的优化就是，我们把num[i]个第i类大米看成下面k+1种物品:

1个(i类物品) 2个 4个$ 2{(k-1}$个以及 $num[i]-2^k+1$ 个

也就是整个区间内的所有数都可以唯一的用这些2的指数幂表示，且每个数字最多用一次，这样时间复杂度就降低到 $O(log n)$ 。

我们对上述k+1种新物品每个都做一个01背包即可覆盖我们可能对第i种物品做出的所有选择.

最终所求: dp[m][n]的值.

HDU-2191 买大米（动态规划 多重背包）¶