hdu 3466 Proud Merchants 带限制的01背包

缘起

带限制的01背包~ hdu 3466 Proud Merchants

分析

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
买东西，每个东西有三个特征值，p代表价格，q代表你手中钱必须不低于q才能买这个物品，v代表得到的价值。
输出最大价值

【输入】
多样例. 每个样例开始于n和m, n表示物品个数, m表示钱数
1 ≤ N ≤ 500, 1 ≤ M ≤ 5000
然后n行,每行包含3个整数, Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000)

【输出】
对每个样例，输出最大价值

【样例输入】
2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3

【样例输出】
5
11

【限制】
1s

本题是带限制的01背包问题, 这里的限制就是购买一件物品之前, 前提是你手上有q块钱. 而经典的01背包是无所谓购买顺序的. 所以才能按照第一件、第二件、…、第n件这一步的顺序去购（D）买（P）. 但是本题不一样, 例如下面两件商品

1
2
A：p1=5, q1=10, v1=5;
B：p2=3, q2=5,  v2=6;

则如果按照先买A、再买B的顺序的话, 需要10块钱. 但是如果反过来, 先买B再买A的话, 则就需要13元钱了. 所以购买顺序不同, 虽然最终获取的价值都是5+6=11, 但是花费的代价不同.

所以我们知道了, 如果假设最后的购买序列是 (p1,q1,v1),…,(pn,qn,vn)的话, 则相邻物品必定满足（和上面的推导一模一样） pi+q_{i+1}<p_{i+1}+qi (左边是先买i再买i+1要准备的钱, 右边是先买i+1再买i的钱) ， 即 pi-qi<p_{i+1}-q_{i+1}

所以我们就知道了, 只需要按照p-q升序排序, 就是正确的购买物品的顺序. 而物品购买的顺序和01背包顺序是相反的. 你想想怎么打印01背包最优解方案就知道了（【2】或者【3】或者《背包九讲2.0》9.1小节）——是从i=n开始反向遍历的! 即最先确定买的物品其实是dp顺序的最后那一个物品. 所以与其这样, 不如我们按照 q-p升序排序（和按照p-q升序是反序的）, 则这个顺序就是dp的顺序了.

注意, 这里的分析和【1】是一样的.

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
45
46
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 505, maxv = 5005;
struct Goods
{
	int p,q,v;
	bool operator <(Goods &o)
	{
		return q-p<o.q-o.p;
	}
}g[maxn];
int n,m,dp[maxv]; // dp[j] 是仅仅考虑前i个物品, 容量为j的时候, 最大价值

void zo(int i)
{
	for (int v = m;v>=max(g[i].p, g[i].q); v--)
	{
		dp[v] = max(dp[v], dp[v-g[i].p]+g[i].v);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n,&m))
	{
		memset(dp,0, sizeof(dp));
		for (int i = 1;i<=n;i++)
		{
			scanf("%d%d%d", &g[i].p, &g[i].q, &g[i].v);
		}
		sort(g+1,g+n+1);
		for (int i = 1;i<=n;i++)
		{
			zo(i);
		}
		printf("%d\n", dp[m]);
	}
	return 0;
}

ac情况

Status Accepted
Time 46ms
Memory 1780kB
Length 750
Lang C++
Submitted 2019-10-27 20:34:34
Shared
RemoteRunId 31140430

本题说明——死套背包模板是没有出路的~ 必须要理解01背包算法.

参考

【1】https://yfsyfs.github.io/2019/08/15/51nod-1205-%E6%B5%81%E6%B0%B4%E7%BA%BF%E8%B0%83%E5%BA%A6-Johnson%E7%AE%97%E6%B3%95/

【2】https://yfsyfs.github.io/2019/10/26/2017%E7%99%BE%E5%BA%A6%E4%B9%8B%E6%98%9F%E8%B5%84%E6%A0%BC%E8%B5%9B-hdu6083-%E5%BA%A6%E5%BA%A6%E7%86%8A%E7%9A%84%E5%8D%88%E9%A5%AD%E6%97%B6%E5%85%89-01%E8%83%8C%E5%8C%85%E8%BE%93%E5%87%BA%E5%AD%97%E5%85%B8%E5%BA%8F%E6%9C%80%E5%B0%8F%E8%A7%A3/

【3】https://yfsyfs.github.io/2019/08/19/uva-624-CD-01%E8%83%8C%E5%8C%85-%E8%BE%93%E5%87%BA%E6%9C%80%E4%BC%98%E6%96%B9%E6%A1%88%E6%A8%A1%E6%9D%BF/