hdu_3466(01背包)
2024-10-07 06:35:38
其实,就是让C商品的q不等于p,其他都相同,这时,你就会发现如果要买C商品的话,肯定得先买C商品,因为买C商品的代价最大。所以,我们可以按照qi-pi的顺序来确定大顺序。这里我们还可以用更严谨的方式来证明一下,比如A:p1 q1, B:p2 q2,然后,假设单独买A或者B的话,都是可以买到的。这时,若先买A,则你至少需要p1+q2的钱;若先买B,则至少需要p2+q1的钱。那肯定是花最少的钱咯,所以如果先买A再买B,那么p1+q2<p2+q1,转换一下,就是q1-p1>q2-p2,也就是说qi-pi大的先买。这里还得注意一点就是,排序的时候,得按照qi-pi从小到大排序,因为你买第n件商品的时候,是在比较你是否要先买第n件商品。打个比方让大家更好地理解,比如说f(3, 10),是不是max(f(2, 10-p3)+v3, f(2, 10)),你会发现这个第一种情况f(2,10-p3)+v3中,是先买了第三件商品,也就是说排在后面的商品会先买。好的,排好序之后,就把问题就转换为不需要考虑顺序的问题了,那就是解决0/1背包问题了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct item{
int p;
int q;
int v;
} I[];
bool cmp(item a,item b){
return a.q-a.p < b.q-b.p;
}
int dp[];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(dp,,sizeof(dp));
for(int i = ; i < n; i++){
scanf("%d%d%d",&I[i].p,&I[i].q,&I[i].v);
}
sort(I,I+n,cmp);
for(int j = ;j < n ;j++){
for(int i = m; i >= max(I[j].q,I[j].p); i--){
dp[i] = max(dp[i],dp[i-I[j].p]+I[j].v);
}
}
printf("%d\n",dp[m]);
} return ;
}
最新文章
- Hibernate个人学习笔记(2)
- centos 6.4下安装postgresql 9.2
- 【Oracle XE系列之三】使用OMF方式手工创建Oracle XE数据库
- IIS ,未能加载文件或程序集“System.Web.DataVisualization, Version=3.5.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35”或它的某一个依赖项。系统找不到指定的文件。
- Codeforces Round #262 (Div. 2) B
- haproxy 配置日志
- 如何增强ArcGIS插值图出图效果
- 转: 【Java并发编程】之十三:生产者—消费者模型(含代码)
- 强化学习(三)用动态规划(DP)求解
- 位运算之——按位与(&;)操作——(快速取模算法)
- 微信小程序:图片预览
- hdu6024 Building Shops(区间dp)
- Linux Centos下查看cpu、磁盘、内存使用情况,关闭MySQL日志
- 【做题】agc003E - Sequential operations on Sequence——经典结论
- JavaScript callback function 回调函数的理解
- windows 网管常用命令
- jsp 页面和 jsp标记
- java8 - 3
- [NPM] Execute npx commands with $npm_ Environment Variables
- 基于jquery ui修改的不依赖第三方的背景透明的弹出div