Solutions of Knapsack

Select solution language

Write solution here.

bean Created at 11 likes

Có khoảng tối đa

$\sqrt{2 * T}$ các giá trị

$w$ khác nhau trong mảng, vậy ta có thể đếm số lần một giá trị

$w$ xuất hiện. Gọi

$c_i$ là số lần giá trị

$w_i$ xuất hiện với

$i \in [1, T]$ Khi này bài toán sẽ trở thành bài toán knapsack cổ điển như sau: cho các cặp giá trị

$w_i$ và

$c_i$ , hỏi ta có thể tạo ra

$x$ từ các cặp số này hay không? Biết rằng mỗi

$w_i$ được sử dụng tối đa

$c_i$ lần. Nó sẽ gần giống với bài này: https://marisaoj.com/problem/156 Với mỗi giá trị

$i$ , ta chia nhỏ

$c_i$ thành tổng của

$2^x$ sao cho cộng lại bằng đúng

$c_i$ , với mỗi giá trị

$2^x$ , ta sẽ có thể tạo thành giá trị

$w_i * 2^x$ . Độ phức tạp sẽ là

$\mathcal{O}(T\sqrt{2 * T})$ Do chúng ta chỉ cần kiểm tra xem việc tạo thành

$i$ là thực hiện được hay không, ta có thể dùng bitset để thực hiện các thao tác tính toán một cách nhanh hơn, giảm được độ phức tạp xuống

$\mathcal{O}(\frac{T\sqrt{2 * T}}{32})$ Code tham khảo:

$cpp #include "bits/stdc++.h" using namespace std; bitset<(int)1e6 + 1> dp; int main() { cin.tie(0)->sync_with_stdio(0); int n, T; cin >> n >> T; vector<int> w(n); for (int i = 0; i < n; i++) { cin >> w[i]; } sort(w.begin(), w.end()); dp[0] = 1; for (int i = 0; i < n;) { int nxt = upper_bound(w.begin(), w.end(), w[i]) - w.begin(); int c = nxt - i; for (int k = 1; c > 0; k <<= 1) { int x = min(k, c); c -= x; dp |= dp << (w[i] * x); } i = nxt; } for (int i = 1; i <= T; i++) { cout << dp[i]; } }$