古代王国寻宝问题
题目描述
最近，iSea来到了一个古老的国度。曾几何时，这里是世界上最富有、最强大的王国。即便现在不再那么富裕，这里的人民依然骄傲自豪。
这里的商人们各有特色，每人只卖一样宝贝，售价是 Pi，但如果你身上的钱少于 Qi，他们可不卖给你哦。iSea给每件宝贝都评了个价值 Vi。
如果他手头有 M 单位的钱，最多能收获多大价值呢？
输入格式
输入包含多个测试用例。
每个测试用例格式：
第一行有两个整数 N、M：
- N：宝贝数量 (1 ≤ N ≤ 500)
- M：初始资金 (1 ≤ M ≤ 5000)
接下来有 N 行，每行三个数字 Pi、Qi、Vi：
- Pi：宝贝的售价 (1 ≤ Pi ≤ Qi ≤ 100)
- Qi：购买所需的最低资金门槛 (1 ≤ Pi ≤ Qi ≤ 100)
- Vi：宝贝的价值 (1 ≤ Vi ≤ 1000)
输出格式
对每个测试用例，输出一个整数，表示 iSea 能获得的最大价值。
输入输出样例
输入样例
2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3
输出样例
5
11
约束条件
| 参数 | 范围 | 说明 |
|---|---|---|
| N | 1 ≤ N ≤ 500 | 宝贝数量 |
| M | 1 ≤ M ≤ 5000 | 初始资金 |
| Pi | 1 ≤ Pi ≤ Qi ≤ 100 | 宝贝售价 |
| Qi | 1 ≤ Pi ≤ Qi ≤ 100 | 购买门槛 |
| Vi | 1 ≤ Vi ≤ 1000 | 宝贝价值 |
题解
每人只卖一样宝贝，售价是 Pi，但如果你身上的钱少于 Qi，每人只卖一样宝贝，售价是 Pi，但如果你身上的钱少于 Qi，他们可不卖给你哦.
- 取消Q_i,限制，问题转化为01背包问题
- 核心问题在于确定一种购买顺序，如果存在一个购买方案，vi>=Qi
F[i][v] ,对于物品i,空间v的最大获利为F[i][v].v>Qi, 才能购买第i个物品。
思考：\(Q_i-P_i\) 为冗余的购买力。从小到大排序，这样可以最大化资金利用率。
样例分析
输入：
3 10
5 10 5 (售价5，门槛10，价值5)
3 5 6 (售价3，门槛5，价值6)
2 7 3 (售价2，门槛7，价值3)
输出：11
分析（排序后）：
- 排序：按(Qi-Pi)差值排序： 宝贝2：Qi-Pi=2 (门槛5-售价3) 宝贝3：Qi-Pi=5 (门槛7-售价2) 宝贝1：Qi-Pi=5 (门槛10-售价5)
- 购买顺序： 买宝贝2(3,5,6)：花费3元，获得6价值，剩余7元 买宝贝3(2,7,3)：花费2元，获得3价值，剩余5元 买宝贝1(5,10,5)：无法购买（门槛10 > 剩余5）
- 总价值：6 + 3 = 9
但最佳方案是：
- 只买宝贝1和宝贝2： 先买宝贝2：花费3元，获得6价值，剩余7元 买宝贝1：花费5元，获得5价值，剩余2元
- 总价值：6 + 5 = 11
代码
#include <bits/stdc++.h>
using namespace std;
int n,m,f[5005];
struct node {int p,q,v;
}s[501];int main() {while (scanf("%d%d",&n,&m)==2) {for (int i=1;i<=n;i++) scanf("%d%d%d",&s[i].p,&s[i].q,&s[i].v);sort(s+1,s+1+n,[](node t1,node t2){return t1.q-t1.p<t2.q-t2.p;});memset(f,0,sizeof(f));for (int i=1;i<=n;i++)for (int j=m;j>=s[i].q;j--)f[j]=max(f[j],f[j-s[i].p]+s[i].v);cout<<f[m]<<endl;}return 0;
}