Hướng dẫn giải của Atcoder Educational DP Contest E - Knapsack 2

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: 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;
        }
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 47
    Motconmeocon  đã bình luận lúc 7, Tháng 6, 2023, 4:15 ← sửa 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;

  • 72
    reddevils2709  đã bình luận lúc 28, Tháng 2, 2023, 12:45 ← chỉnh sửa

    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  đã bình luận lúc 27, Tháng 9, 2022, 10:06 ← chỉnh sửa

    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 ạ


    • -11
      reddevils2709  đã bình luận lúc 25, Tháng 2, 2023, 18:27

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -18
      reddevils2709  đã bình luận lúc 25, Tháng 2, 2023, 18:01

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.