UVa 10130 : SuperSale

Posted on | In |  
Symbols : 334 字

有 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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
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;
}
0%