Cho mảng p, c kích thước D và mục tiêu G. Bài độ khó i: điểm 100*i, có p[i] bài. Giải hết bài độ i được thưởng c[i]. Tìm số bài tối thiểu để đạt ≥ G điểm.
Ví dụ
Với G=500, P=[3,5], C=[500,800], đầu ra 3.
Giải thuật
Duyệt mọi tập con các độ khó giải hoàn toàn (bitmask). Với tập con đã chọn, tính điểm và số bài. Nếu chưa đủ G, giải thêm bài độ khó cao nhất chưa chọn hoàn toàn. Lấy min số bài trên tất cả trường hợp.
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(int G, vector<int> p, vector<int> c) {
int D = p.size();
int mi = 10000;
for (int i = 0; i < 1 << D; i++) {
int sum = 0, count = 0, at = 0;
bitset<10> b(i);
for (int j = 0; j < D; j++) {
if (b.test(j)) {
count += p[j];
sum += (j + 1) * 100 * p[j] + c[j];
} else at = j;
}
if (sum < G) {
int d = (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100);
if (d <= p[at]) {
sum += (at + 1) * 100 * d;
count += d;
}
}
if (sum >= G) mi = min(mi, count);
}
return mi;
}
int main() {
int G = 500;
vector<int> P = { 3, 5 }, C = { 500, 800 };
cout << solve(G, P, C) << endl;
}
Đầu vào / Đầu ra
Input: 500, { 3, 5 }, { 500, 800 }
Output: 3