# Ý tưởng
Bài toán yêu cầu chọn một tập con các món đồ sao cho: Tổng cân nặng ≤ S và giá trị tổng là lớn nhất.
Với n ≤ 20, ta có thể duyệt toàn bộ các tập con của n món (tối đa 2^n ≈ 1 triệu, chạy được).
## Ta viết hàm đệ quy dequy(idx, g, s) với:
idx: chỉ số món đang xét.
g: tổng cân nặng hiện tại.
s: tổng giá trị hiện tại.
## Ở mỗi bước:
Không chọn món idx → sang món idx+1.
Chọn món idx nếu g + w[idx] ≤ S → sang món idx+1 với cân nặng và giá trị mới.
Khi idx > n, cập nhật kết quả ans = max(ans, s).
## code tham khảo, nên tự viết lại, không nên copy bạn nhé!!!
```cpp
#include <bits/stdc++.h>
#define io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FOR(i, a, b, k) for(int i = a; i <= b; i += k)
using namespace std;
int n;
long long S, w[22], v[22], ans;
void dequy(int idx, long long g, long long s) {
if (g > S) return;
if (idx == n+1) {
ans = max(ans, s);
return;
}
///không chọn món thứ idx
dequy(idx+1, g, s);
///chọn món thứ idx
if (g + w[idx] <= S)
dequy(idx+1, g + w[idx], s + v[idx]);
}
void sol() {
cin >> n >> S;
FOR(i, 1, n, 1) cin >> w[i] >> v[i];
ans = 0;
dequy(1, 0, 0);
cout << ans;
}
int main() {
io
#define NAME "test"
if (fopen(NAME".inp", "r")) {
freopen(NAME".inp", "r", stdin);
freopen(NAME".out", "w", stdout);
}
sol();
return 0;
}
```
peter_nguyen
Created at
1 likes