UVa 12551 - Shares

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

現在要購買股票,每一個股票都有其花費和預期的在未來的出售價格。

但是股票採用組合包的方式進行販售,但是每一種組合包都只能購買一次,請問在資金只有 C 元的情況下,最多能在未來淨利多少。

Sample Input

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
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30

Sample Output

1
2
52
2168800

Solution

每個東西只能購買一次,可見是一個 01 背包問題,但是由於 C 很大,也就是背包容量過大,導致 DP 上的困難。

但是題目並沒有特別說明測資的特殊性,後來才得知可以用 gcd 最大共同因數去降,就是縮小幣值,相當於換外國幣去思考。這麼一來 C 可以降很多,但在一般的背包問題中,gcd 的效應並不高。

把我的純真還回來啊,不想自己 yy 測資特殊性。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int C, n, m;
int x, s, q;
int cost[512], profit[512];
int cases = 0;
while (scanf("%d", &C) == 1) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d %d", &cost[i], &profit[i]), profit[i] -= cost[i];
vector< pair<int, int> > items;
for (int i = 0; i < m; i++) {
scanf("%d", &x);
int c = 0, p = 0;
for (int j = 0; j < x; j++) {
scanf("%d %d", &s, &q);
c += cost[s] * q;
p += profit[s] * q;
}
if (c <= C && p > 0)
items.push_back(make_pair(c, p));
}
if (cases++) puts("");
if (items.size() == 0) {
puts("0");
continue;
}
if (items.size() == 1) {
printf("%d\n", items[0].second);
continue;
}
int g = C;
for (int i = 0; i < items.size(); i++)
g = __gcd(g, items[i].first);
C /= g;
for (int i = 0; i < items.size(); i++)
items[i].first /= g;
vector<int> dp(C + 1, 0);
for (int i = 0; i < items.size(); i++) {
for (int j = C; j >= items[i].first; j--)
dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second);
}
printf("%d\n", dp[C]);
}
return 0;
}
/*
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30
*/