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.

Author: NoobCpp

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

Please read the guidelines before commenting.

1
reddevils2709 commented on Feb. 28, 2023, 12:45 p.m.
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:

Nếu không chọn gói i: dp[i][j] = dp[i - 1][j]

Nếu có chọn gói i: dp[i][j] = dp[i - 1][j - v[i]] + w[i] (tất nhiên chỉ xét khi v[i] ≤ j) Vì ta muốn dp[i][j] là nhỏ nhất có thể nên dp[i][j] sẽ là min của một trong hai trường hợp ở trên

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:((((((

0

thaihoang78 commented on Sept. 27, 2022, 10:06 a.m. ← edited →

cho em hỏi là vì sao đoạn duyệt quy hoạch động (đoạn có 2 vòng i và j) thì mình cho j chạy từ mx-1 -> 0 mà không phải 0 -> mx-1 vậy ạ

-4

reddevils2709 commented on Feb. 25, 2023, 6:27 p.m.

à 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

-2

reddevils2709 commented on Feb. 25, 2023, 6:01 p.m.

mình cũng không biết