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.

43
Motconmeocon commented on June 7, 2023, 4:15 a.m. ← edit 3 →
Gọi dp[i][v] là khối lượng nhỏ nhất để có được giá trị (v) khi xét qua (i) đồ vật.

Ta nhận thấy giá trị (v) sẽ được cân nhắc là đáp án khi tồn tại một cách chọn đồ vật sao cho tổng bằng (v).

Trường hợp cơ sở :

dp[i][val[i]] = wei[i] , để tạo tổng giá trị là val[i] thì cần có ít nhất wei[i] , tất nhiên về sau dp[i][val[i]] vẫn có thể bị thay đổi.

dp[i][0] = 0 , tạo tổng giá trị là 0 thì chỉ cần khối lượng 0.

Trường hợp khác, dp[i][v] = W + 1 ( để ta cực tiểu hóa dần ).

Đáp án bài toán là giá trị (v) lớn nhất sao cho dp[N][v] <= W .

Tức là với dp[i][v] , ta có :

dp[i][v] = dp[i-1][v]

dp[i][v] = min(dp[i][v], dp[i][ v - val[i] ] + wei[i] ) , thử tạo tổng (v) bằng đồ vật thứ (i) thì khối lượng tăng thêm wei[i].

Nếu muốn tối ưu bộ nhớ, hãy lại chuyển thành 2 mảng con :) hoặc như lời giải mẫu chỉ cần 1 mảng , ở đây mình có code đã AC :

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N,W; cin >> N >> W; int grtVal = 0; for (int i = 1 ;i <= N ; ++i) { cin >> ar[i].f >> ar[i].s; grtVal += ar[i].s; } for (int i = 0 ; i <= N ; ++i) for (int v = 0 ; v <= grtVal; ++v) dp[i][v] = W + 1; for (int i = 1 ; i <= N; ++i) dp[i][0] = 0, dp[i][ar[i].s] = ar[i].f; for (int i = 1 ; i <= N; ++i) { for (int v = 1 ; v <= grtVal; ++v) { dp[i][v] = min(dp[i][v] , dp[i-1][v]); if (v >= ar[i].s) dp[i][v] = min(dp[i][v],dp[i-1][v - ar[i].s] + ar[i].f); } } int ans = 0; for (int v = 1 ; v <= grtVal; ++v) if (dp[N][v] <= W) ans = v; cout << ans;

63
reddevils2709 commented on Feb. 28, 2023, 12:45 p.m. ← edited →
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:((((((

1

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 ạ

-12

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

This comment is hidden due to too much negative feedback. Show it anyway.

-19

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

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

This comment is hidden due to too much negative feedback. Show it anyway.