HDOJ 2191 珍惜现在，感恩生活 【动态规划 多重背包】

题目链接：

　　http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20468

---

题目描述：

　　现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
　　请问：你用有限的资金最多能采购多少公斤粮食呢？

　　输入数据首先包含一个正整数C，表示有C组测试用例，

　　每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，

　　然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1& lt;=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

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

---

思路：

　　因为数量有限制，所以输入的时候用二进制分割转化成多个单一的temp*v0 temp*w0的形式的大米

　　之后使用01背包求解即可

　　因为不要求花光所有经费，初始化dp全为0即可（全花光经费的话，初始化dp[0] = 0; dp[>0] = INF）

---

多重背包：

　　转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。

　　仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略

　　　　——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。

　　方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。

　　使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。

　　例如，如果n[i]为13，就将这种 物品分成系数分别为1,2,4,6的四件物品。

　　分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。

　　另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难。

　　这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为<math>O(V*Σlog n[i])的01背包问题，是很大的改进。

　　下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

procedure MultiplePack(cost,weight,amount)

    if cost*amount>=V

        CompletePack(cost,weight)

        return

    integer k=1

    while k<amount

        ZeroOnePack(k*cost,k*weight)

        amount=amount-k

        k=k*2

    ZeroOnePack(amount*cost,amount*weight)

---

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXL = 5*100+10;
int t, money, n, newsum, value[MAXL], weight[MAXL], num[MAXL], dp[105];
int v0, w0, n0;

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &money, &n);
        newsum = n;
        int pos = 0;
        while(n--){
            scanf("%d%d%d", &v0 ,&w0, &n0);
            int temp = 1;
            while(n0 >= temp){
                value[pos] = temp*v0;
                weight[pos++] = temp*w0;
                n0 -= temp;
                temp <<= 1;
                newsum++;
            }
            value[pos] = n0*v0;
            weight[pos++] = n0*w0;
        }
        //puts("---");
        //for(int i = 0; i < newsum; i++) printf("%d	%d
", value[i], weight[i]);
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < newsum; i++){
            for(int j = money; j >= value[i]; j--){
                dp[j] = max(dp[j], dp[j-value[i]]+weight[i]);
            }
        }
        printf("%d
", dp[money]);
    }

    return 0;
}