HDU 3446 有贪心思想的01背包
Proud Merchants
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 4500 Accepted Submission(s): 1873
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?
Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.
The input terminates by end of file marker.
因为这个题目增加了购买的前提条件,和普通的01背包有点不同;
哪里不同呢?不同的地方在于普通的01背包,购买顺序不影响其结果;
但是在这里,我们可以很明白的看出来,购买顺序是会影响我们的最后结果的。
所以我们应该确定一个正确的购买顺序;然后我们就可以想想,如果叫你判断买不买,
实现价值最大化,你会以怎样的顺序先后判断;
很显然,你会先判断q大,p小的物品买不买,对吧,因为在你价值最大,你应该尽可能的判断q大,p小的物品;
明白这点,这个题目基本上就解决了;
我们可以对数据进行排序,直接就以p,q的差值排序就可以了;
但是这里我们需要注意的是,要以差值由小到大排序,而不是由大到小,
想想dp的过程,j=m,j--;后取得数在前面判断,这样才能让我们的数据更新不被影响;
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#define ll __int64
#define pi acos(-1.0)
#define mod 1
#define maxn 10000
using namespace std;
int n,m;
struct node
{
int p,q,v;
}N[];
int dp[];
bool cmp(struct node aa,struct node bb)
{
if((aa.q-aa.p)<(bb.q-bb.p))
return true;
return false;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(dp,,sizeof(dp));
memset(N,,sizeof(N));
for(int i=;i<=n;i++)
scanf("%d %d %d",&N[i].p,&N[i].q,&N[i].v);
sort(N+,N++n,cmp);
for(int i=;i<=n;i++)
{
for(int l=m;l>=N[i].q;l--)
dp[l]=max(dp[l],dp[l-N[i].p]+N[i].v);
}
cout<<dp[m]<<endl;
}
return ;
}
最新文章
- BPM配置故事之案例11-操作外部数据源
- zepto和jquery的区别,zepto的不同使用8条小结
- java:利用xpath删除xml中的空节点
- _mkdir
- java微信开发(wechat4j)——access_token中控服务器实现
- SET ANSI_NULLS ON
- ZOJ Problem Set - 3758 素数
- linux的文本管道连接处理技巧
- PowerShell 中的目录文件管理
- Windows权限提升基础知识和命令
- oracle12c各个版本对其需要的依赖包及系统参数的修改
- Android编写点击TextView拨打电话
- vue-百度地图-maker文字标签显示隐藏
- Android项目实战(四十八):架构之组件化开发
- 《分布式任务调度平台XXL-JOB》
- TortoiseSVN 1.9.5安装 与 Eclipse4.4.2及以上版本中安装SVN插件
- JAVA WEB ------ 文件下载及导出数据到office Execl表格
- Corel Video Studio Pro X5
- golang安装开发环境配置
- SQL Server IF Exists 判断数据库对象是否存在的用法