同題：UVa 10130 – SuperSale
有間商店共有 N 種商品每種商品有不同的重量和價值且每人每種最多只能拿一個。
求出 G 個人最大能拿走多少價值的商品。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有個 T 代表測資數目 (1 ≤ T ≤ 1000) 每筆次測資第一行有個數字 N 代表商品數目 (1 ≤ N ≤ 1000)。 接下來 N 行有 P 和 W 分別代表商品的價值和重量。 之後有一行 G 代表有 G 個人 (1 ≤ G ≤ 100)。 接下來 G 行有每個人的負重 (皆小於等於 30)。 | 輸出最大能拿走多少價值的商品。 |
| 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 | 72 514 |
解題思路
尋找所有人中承受重量的最大值，並且用其數字做 0 1 背包的問題並且生成 Map，對每個人能承受的重量往下找到最大值。
範例程式碼－ZeroJudge F440: SuperSale
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N;
cin >> N;
int W[1000] = {};
int P[1000] = {};
for (int j = 0; j<N; j++) {
cin >> P[j] >> W[j];
}
vector<int> people;
int G, maxx = -999;
cin >> G;
for (int j = 0; j<G; j++) {
int tmp;
cin >> tmp;
people.push_back(tmp);
maxx = max(maxx, tmp);
}
map<int, int>ans;
for (int j = 0; j<N; j++) {
int w = W[j] , p = P[j];
for (int k = maxx; k>=w; k--) {
ans[k] = max(ans[k], ans[k-w]+p);
}
ans[w] = max(p, ans[w]);
}
int sum = 0;
for (int j = 0; j<people.size(); j++) {
int maxx = -999;
for (int k = people[j]; k>=0; k--) {
maxx = max(maxx, ans[k]);
}
sum += maxx;
}
cout << sum << "\n";
}
}
//ZeroJudge F440
//Dr. SeanXD