有 N 項商品，每個價值為 Vi 且重量為 Wi，並有 G 個人，每個人的最大負重為 Qj，若每個人每種商品只能取一件，求所有人在自己的負重內可以取得的最大價值的總和。
測資
Input :
2
3
72 17
44 23
31 24
1
26
6
64 26
85 22
52 4
99 18
39 13
54 9
4
23
20
20
26
Output :
72
514
解法
此題就是 01 背包問題
程式碼
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
|
#include <vector>
#include <algorithm>
using namespace std;
class
{
public:
Solution() : val(1000)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int calculate(const vector<pair<int, int>> &data, const vector<int> &mw, const int Max_Volumn)
{
initial(Max_Volumn);
int i, k;
for (i = 0; i < data.size(); ++i)
for (k = Max_Volumn; k >= data[i].second; --k)
val[k] = max(val[k], val[k - data[i].second] + data[i].first);
int sum = 0;
for (auto x : mw)
sum += val[x];
return sum;
}
private:
vector<int> val;
void initial(const int Max_Volumn)
{
val.clear();
val.resize(Max_Volumn + 1, 0);
}
};
int main(void)
{
int total_case;
int n;
int price, weight;
int n_people;
int max_w;
int m;
int ans;
Solution s;
vector<pair<int, int>> data(1000);
vector<int> mw(100);
cin >> total_case;
while (total_case--)
{
cin >> n;
data.clear();
mw.clear();
while (n--)
{
cin >> price >> weight;
data.emplace_back(price, weight);
}
cin >> n_people;
m = -1;
while (n_people--)
{
cin >> max_w;
if (max_w > m)
m = max_w;
mw.emplace_back(max_w);
}
ans = s.calculate(data, mw, m);
cout << ans << endl;
}
return 0;
}
|
近期评论