题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3466
题目大意:给定n个物品和钱m,每个物品有价格p,限制钱数q,价值v,限制q的意思是你手头的前必须大等于q才能装买这个物品,问最后获得的最大价值。n<=500,m<=5000.
解题思路:与顺序有关的01背包。初看之下似乎和普通背包差不多,判容量大于q时才装。但是这会出大问题,如果一个物品p
= 5,q = 7,一个物品p = 5,q = 9,如果先算第一个,那么当次只有7,8...m可以进行状态转移,装第二个物品的时候9,10..m进行转移,第二个物品转移就可以借用第一个物品的那些个状态,而第二个物品先转移,第一个再转移则不能。当然,还有价格有关,当限制一样价格不同时顺序就影响结果。
最开始我的排序策略是先按限制从到大排,再按价格从大到小排,这样排序我自己出了两组测试数据和题目给的数据结果都是正确的,但是下面测试数据中的第一组数据过不了。然后就拼命想排序策略,想到一种组合的排序策略--限制又小价格又贵的先选,也就是q-p小的先选。为什么这样呢?A:p1,q1 B: p2,q2,先选A,则至少需要p1+q2的容量,而先选B则至少需要p2+q1,如果p1+q2>p2+q1,那么要选两个的话的就要先选A再选B,公式可换成q1-p1
< q2-p2,就按这样的方法排序最后的顺序就是最优的顺序。
这题换成多重背包可以用同样的方法处理。
测试数据:
3 11
3 4 1
4 3 1
5 5 2
3 10
5 10 5
3 5 6
2 0 3
3 8
5 4 5
3 4 6
2 4 3
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MIN 510
#define MAX 5100
struct node {
int p,q,v;
}arr[MIN];
int dp[MAX],n,m;
int cmp1(node a,node b) {
if (a.p == b.p) return a.q < b.q;
return a.p > b.p;
}
int cmp2(node a,node b) {
if (a.q == b.q) return a.p > b.p;
else return a.q < b.q;
}
int cmp3(node a,node b) {
return (a.q - a.p) < (b.q - b.p);
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m) != EOF) {
for (i = 1; i <= n; ++i)
scanf("%d%d%d",&arr[i].p,&arr[i].q,&arr[i].v);
memset(dp,0,sizeof(dp));
sort(arr+1,arr+1+n,cmp3);
for (i = 1; i <= n; ++i)
for (j = m; j >= arr[i].p; --j)
if (j >= arr[i].q)
dp[j] = max(dp[j],dp[j-arr[i].p]+arr[i].v);
printf("%d\n",dp[m]);
}
}
本文ZeroClock原创,但可以转载,因为我们是兄弟。
分享到:
相关推荐
杭电hdu acm资料所用杭电的acm题
动态规划DP题解 POJ HDU部分动态规划DP题解
此程序为hdu的acm2010题,就是解决水仙花数问题
HDU_ACM_1002_大数相加C源代码,利用字符串处理
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
数字图像处理_hdu_期末复习资料_试卷等.zip
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
杭电acm解题报告 详细解析2000-2099 适合acm初学者
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?...
写一个数据结构算法,杭电上一道题目,有关数据结构的题目。
关于矩阵变换,四元数计算的一些实现,结合Phantom设备。
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
hdu_2102_passed_sorce
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
题目链接题目意思给你n个点,让你在这n个点之间加边,但是不管咋加都不能形成三个点的直接相通环,让求最大的边数。要求最大的边数还不能出现三个边的环,我们可以将n个
HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
杭电oj4405,一道简单的概率dp题目
模式识别_hdu_期末复习资料集合_试卷笔记.zip