动态规划题集

01背包问题

HDU-3466

题目: HDU-3346. Proud Merchants

分析:  首先对于任意两个物品i和j,如果我们只选他们中的一个或全不选,我们所需要的初始金钱是相同的.现在如果我们对于它们两个都选,初始金钱就跟选择的顺序有关了.比如:

3 5 6

5 10 5

两个物品,如果先1后2,初始需要13,如果先2后1,初始需要10.

对于任意两个物品i和j,如果我们先i后j初始:

金钱= Q[i]+Q[j]-(Q[i]-p[i]) = p[i]+Q[j]

同理可得先j后i,初始:

金钱= Q[j]+Q[i]-(Q[j]-p[j]) = p[j]+Q[i]

所以对于i和j,假设我们手上有M金钱,我们肯定先以(Q-P)值从大到小开始选择,这样我才能保证对于同一种选择方案(某些选,某些不选),我们所需要的初始金钱最小.或者换一种说法,给定一定的金额,如果按照(Q-P)值从大到小的顺序进行选择,可以获得尽可能多的物品.

solution:  01背包+贪心,关键在于找到要进行贪心的值

implementation:

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
47
48
49
50
/*******************************************************************************
Author: liujian
Email: brooksj@foxmail.com
Date: 2019-07-18 10:51
File: hdu_3466.cpp
Last modified: 2019-07-18 10:51
*******************************************************************************/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5 * 1e2 + 1;
const int maxm = 5 * 1e3 + 1;

struct item {
int p, q, v;
item(int _p = 0, int _q = 0, int _v = 0):p(_p),q(_q),v(_v){}
friend bool operator < (const item &a, const item &b) {
return (a.q - a.p) < (b.q - b.p);
}
};

int dp[maxm], sum[maxn];
item items[maxn];

int main() {
ios_base::sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
sum[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> items[i].p >> items[i].q >> items[i].v;
}
sort(items + 1, items + n + 1);
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + items[i].p;
}
for (int i = 0; i <= m; i++) {
dp[i] = 0;
}
for (int i = 1; i <= n; i++) {
int lowerb = max(max(m - sum[n] + sum[i], items[i].p), items[i].q);
for (int j = m; j >= lowerb; j--) {
dp[j] = max(dp[j], dp[j - items[i].p] + items[i].v);
}
}
cout << dp[m] << endl;
}
return 0;
}
---------------- The End ----------------

作者: brooksjay
联系邮箱: jaypark@smail.nju.edu.cn
本文地址: https://brooksj.com/2019/07/18/动态规划题集/
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
转载请注明出处, 谢谢!