Solutions of Knapsack 2

Select solution language

hungkm466 Created at 0 likes

# Hướng dẫn Gọi **f[i][j]** là giá trị lớn nhất có thể lấy được từ **i** món đồ đầu tiên với cái túi có trọng lượng **j**. Đây là bài toán **DP 0-1**, lấy hoặc không lấy.\ **THCS:** dp[0][i] = dp[i][0] = 0 (1 ≤ i ≤ n).\ **TH1:** Không lấy món đồ thứ i. - f[i][j] = f[i-1][j] (w[i] > j) **TH2:** Lấy món đồ thứ i. - f[i][j] = max(f[i-1][j], f[i-1][j - w[i]] + v[i]). Ta chỉ lấy được món đồ thứ i khi cái túi j còn chỗ trống : w[i] ≤ j. **Code:** O(n * S) ``` #include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for (int i=a; i<=b; ++i) const int MAXN = 1e2 + 5; const int MAXS = 1e5 + 5; int n,S; int w[MAXN], v[MAXN]; int f[MAXN][MAXS]; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> S; FOR(i,1,n) cin >> w[i] >> v[i]; FOR(j,1,S) { FOR(i,1,n) if (j >= w[i]) f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]); else f[i][j] = f[i-1][j]; } return cout << f[n][S], 0; } ```