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)

1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int MAXL = 5*100+10; 7 int t, money, n, newsum, value[MAXL], weight[MAXL], num[MAXL], dp[105]; 8 int v0, w0, n0; 9 10 int main(){ 11 scanf("%d", &t); 12 while(t--){ 13 scanf("%d%d", &money, &n); 14 newsum = n; 15 int pos = 0; 16 while(n--){ 17 scanf("%d%d%d", &v0 ,&w0, &n0); 18 int temp = 1; 19 while(n0 >= temp){ 20 value[pos] = temp*v0; 21 weight[pos++] = temp*w0; 22 n0 -= temp; 23 temp <<= 1; 24 newsum++; 25 } 26 value[pos] = n0*v0; 27 weight[pos++] = n0*w0; 28 } 29 //puts("---"); 30 //for(int i = 0; i < newsum; i++) printf("%d\t%d\n", value[i], weight[i]); 31 memset(dp, 0, sizeof(dp)); 32 for(int i = 0; i < newsum; i++){ 33 for(int j = money; j >= value[i]; j--){ 34 dp[j] = max(dp[j], dp[j-value[i]]+weight[i]); 35 } 36 } 37 printf("%d\n", dp[money]); 38 } 39 40 return 0; 41 }

网址：HDOJ 2191 珍惜现在，感恩生活 【动态规划 多重背包】 https://www.yuejiaxmz.com/news/view/896602

相关内容

悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（DP多重背包问题）
珍惜生命感恩生活感悟58句
感恩生活的句子经典语录（感恩生活——珍惜每一个温暖瞬间）
心存感恩的心的句子（感悟人生，珍惜当下）
珍惜生命感恩生活的格言
如何在生活中培养感恩心态(4篇)
如何懂了珍惜？懂得珍惜：让生活闪耀光芒的秘诀!
平凡生活中的真谛：珍惜、感恩与坚韧
学会感恩 感恩生活
算法动态规划01背包问题

随便看看