HDOJ(HDU).2191. 悼念512汶川大地震遇难同胞――珍惜现在,感恩生活 (DP 多重背包+二进制优化)
2024-10-19 22:32:54
HDOJ(HDU).2191. 悼念512汶川大地震遇难同胞――珍惜现在,感恩生活 (DP 多重背包+二进制优化)
题意分析
首先C表示测试数据的组数,然后给出经费的金额和大米的种类。接着是每袋大米的价格,重量和袋数。
每种大米的数量是有限的,应该能看出是多重背包的问题。关键是多重背包的处理方法。对多重背包采用二进制优化的方法。设同种大米的数量为n,每袋的价格为v,那么把同一种大米分别拆成1,2,4,8,16……(直到不够2^n时,剩下的单独分成一组),拆分的价格也分别对应是v,2v,4v,8v,16v。按照这样的方式把所有的大米的拆分好,然后依次放置在同一个数组里面,对这些拆分好的大米,做01背包即可。
代码总览
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define nmax 105
#define INIT(x,y) memset(x,y,sizeof(x))
using namespace std;
int dp[nmax*nmax];
int price[nmax*nmax],weight[nmax*nmax];
int main()
{
//freopen("in.txt","r",stdin);
int C;
scanf("%d",&C);
while(C--){
INIT(dp,0);
INIT(price,0);
INIT(weight,0);
int n,m;
int cnt = 1;
scanf("%d%d",&m,&n);
for(int i =1 ;i<= n;++i){
int pri,wei,num;
scanf("%d%d%d",&pri,&wei,&num);
//二进制优化
for(int j = 1;j<=num; j*=2){
price[cnt] = j*pri;
weight[cnt++] = j*wei;
num-=j;
}
if(num>0){
price[cnt] = num*pri;
weight[cnt++] = num*wei;
}
}
//转换成01背包
for(int k = 0; k<=cnt;++k){
for(int j =m;j>=price[k];j-- )
dp[j] = max(dp[j],dp[j-price[k]]+weight[k]);
}
printf("%d\n",dp[m]);
}
return 0;
}
最新文章
- dsp28377控制DM9000收发数据
- iOS UITextField限制输入数字
- 又发现个.net framework的坑
- 19条ANDROID平台设计规范(转)
- BZOJ4554: [Tjoi2016&;Heoi2016]游戏
- tshark (wireshark)笔记
- GPS导航仪常见术语解释
- window国际化文案
- Winform子窗体刷新父窗体
- ASP.NET - GridView实现点击编辑列
- phpcms替换来源
- Zkui安装
- kubernetes实现用户自定义扩缩容
- (转)Jquery on()事件委派
- EFCodeFirst示例
- WindowsAPI每日一练(1) MessageBoxA
- java定时任务调度工具
- SQL Server复制入门(一)----复制简介 (转载)
- python测试开发django-22.admin首页和title修改
- 告知你不为人知的UDP-连接性和负载均衡