HDU3466
[TOC]
中文题意
给出n个商品,以及自己的钱数m,然后以下n行,每一行给出p,q,v三个数,表示第i个商品的价格,以及最少需要多少钱才能进行购买,和收益
求最大价值
思路
根据HDU2546(饭卡)的经验,我们也不难发现这个题的产品应该也是需要排序的,但是每个商品有两个变量,这个就带来了排序的困难.
如果仅凭直觉,到底是以哪个参数排序为主,哪个参数排序为辅呢?似乎都能举出反例..网上有大神指出,可以这样想: 如果有两个商品A和B,要求分别是p1,q1,p2,q2然后我们手动模拟一下对于这两个数的抉择.比如我们先选A再选B,则初始余额至少需要p1+q2;如果先选B再选A,则初始余额至少要p2+q1.然后我们可以理解为取得相同的收益,成本自然越少越好.所以我们要选取p1+q2和p2和q1中最小的一个,排序函数也就是
1
2
3
bool cmp(B &x,B &y){
return x.p+y.q>x.q+y.p;
}
为了便于书写,我们将其化成
1
2
3
bool cmp(B &x,B &y){
return x.q-x.p < y.q-y.p;
}
这样就得到了正解
我们再看一下从数学角度的分析
我们根据HDU2546给出的思路,我们发现状态转移的函数是这样的
1
2
3
4
5
6
for (int i = 1; i <= n; ++i) {
// 题中说了 p<=q
for (int j = m; j >= b[i].q; --j) {
dp[j] = max(dp[j], dp[j - b[i].p] + b[i].v);
}
}
和01背包没有区别,但是我们分析其查询的数组的范围,我们发现,查询的范围是[m,b[i].q-b[i].p] 也就是q-p越小,其范围越大,所以我们应该让q-p越小的数排在越前面.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstring>
#include<string>
#include <algorithm>
#include <iomanip>
// 参考资料 http://www.mamicode.com/info-detail-1009053.html
// https://www.cnblogs.com/kuangbin/archive/2012/09/14/2685826.html
// 至于按照q-p从小到大排序比较难想到。q-p其实就是不更新的范围，不更新的范围从小到大递增时就不会影响后面的DP了。(从dp转移方程的正确性角度分析
// 一种组合的排序策略--限制又小价格又贵的先选，也就是q-p小的先选。为什么这样呢？A：p1,q1 B: p2,q2，先选A，则至少需要p1+q2的容量，而先选B则至少需要p2+q1，如果p1+q2>p2+q1，那么要选两个的话的就要先选A再选B，公式可换成q1-p1 > q2-p2，就按这样的方法排序最后的顺序就是最优的顺序.(从逻辑角度分析前后顺序分析
using namespace std;
struct B {
int p, q, v;
} b[550];
// 神仙
bool cmp(B &x, B &y) {
return x.q - x.p < y.q - y.p;
}
int dp[5500];
int main() {
int n, m;
while (cin >> n >> m) {
for (int i = 1; i <= n; ++i) {
cin >> b[i].p >> b[i].q >> b[i].v;
}
sort(b + 1, b + n + 1, cmp);
// for (int i = 1; i <= n; ++i) {
// cerr << b[i].p << " " << b[i].q << " " << b[i].v << endl;
// }
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
// 题中说了 p<=q
for (int j = m; j >= b[i].q; --j) {
dp[j] = max(dp[j], dp[j - b[i].p] + b[i].v);
}
}
cout << dp[m] << endl;
}
return 0;
}
启示
面对需要考虑先后顺序的01背包问题,我们应该由数学角度进行排序,以让dp数组不错过最优解
