Editorial for Atcoder Educational DP Contest E - Knapsack 2
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Bài toán này tương tự bài Knapsack 1 ngoại trừ việc thay vì giá trị ~v_i~ lớn, giá trị ~w_i~ trong bài này lớn. Bây giờ, với mỗi ~v_i~, chúng ta cần cực tiểu hóa giá trị ~w_i~, rồi tìm giá trị ~v_i~ lớn nhất có thể đạt được.
Gọi ~dp[i]~ là khối lượng nhỏ nhất có thể đạt được với giá trị ~i~. Công thức sẽ là:
~dp[j + v_i] = min(dp[j + v_i], dp[j] + w_i)~
Độ phức tạp thuật toán: ~O(N ^ 2 V)~.
Code mẫu
#include <bits/stdc++.h> using namespace std; const int mx = 1e5+1; template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; } long long dp[mx]; int w[101], v[101]; int main() { cin.tie(0)->sync_with_stdio(0); int N, W; cin >> N >> W; for(int i = 0; i < N; ++i) cin >> w[i] >> v[i]; for(int i = 0; i < mx; ++i) dp[i] = 1e18; dp[0] = 0; for(int i = 0; i < N; ++i) { for(int j = mx - 1; j >= 0; j--) { if(dp[j] + w[i] <= W) ckmin(dp[j + v[i]], dp[j] + w[i]); } } for(int i = mx - 1; i >= 0; i--) { if(dp[i] != 1e18) { cout << i << endl; break; } } }
Comments
Sau khi nghiền ngẫm kĩ thì mình đã được khai sáng. Bản chất quy hoạch động bài này như sau: Nếu chúng ta gọi dp[i][j] là khối lượng nhỏ nhất có thể đạt được với giá trị j khi chọn trong các gói {1,2,3,..,i}. Các dp[i][j] sẽ được xây dựng như sau:
Dòng 0 của bảng có dạng 0, INF, INF,..., INF. Dùng dòng i để đi tính dòng i + 1. Nhận xét: một ô ở dòng i có thể được tính bằng ô [i - 1][j] (bên trên) hoặc ô [i - 1][j - v[i]] (bên trái so với j). Như vậy thì thứ tự đi tính toán nên là từ trên xuống dưới và trên một hàng thì từ trái sang phải. Cách làm trong đáp án chỉ dùng một mảng một chiều (tự đi tính lại chính nó ở trạng thái kế tiếp). Do tác giả sử dụng cặp j+v[i] (bên phải của j) và j thay vì j và j - v[i] nên trên một hàng thì thứ tự tính toán phải là từ phải sang trái (tức cho j chạy ngược về 0)
Nếu bạn thấy bổ ích xin đừng down vote:((((((
à mình nghĩ là như này: Nếu cho chạy từ mx-1 -> 0 thì cái điều kiện if sẽ không đúng khi j == mx - 1. Nhưng nếu bạn cho j chạy từ 0 thì có thể cái điều kiện đó có thể sẽ thoả khi j chạy tới mx - 1 mà mx - 1 + v[i] >= mx nên dẫn tới việc tràn mảng
mình cũng không biết