Atcoder Educational DP Contest D - Knapsack 1

Xem dạng PDF
Gửi bài giải
Điểm: 0,30 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Người đăng:
NoobCpp
Nguồn bài:
Atcoder Educational DP Contest
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ đồ vật được đánh số từ ~1~ đến ~N~. Đồ vật thứ ~i~ ~(1 \le i \le N)~ có khối lượng là ~w_i~ và giá trị là ~v_i~.

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \le N \le 100)~ và ~W~ ~(1 \le W \le 10^5)~: số lượng đồ vật và sức chứa tối đa của chiếc túi.

~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ ~(1 \le w_i \le W)~ và ~v_i~ ~(1 \le v_i \le 10^9)~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Sample 1

Input
3 8
3 30
4 50
5 60
Output
90

Chọn đồ vật ~1~ và ~3~. Tổng khối lượng sẽ là ~3 + 5 = 8~ và tổng giá trị là ~30 + 60 = 90~.

Sample 2

Input
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
Output
5000000000

Kết quả có thể vượt quá giới hạn kiểu số nguyên ~32~-bit.

Sample 3

Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17

Chọn đồ vật ~2~, ~4~ và ~5~. Tổng khối lượng sẽ là ~5 + 6 + 3 = 14~ và tổng giá trị là ~6 + 6 + 5 = 17~.

Bình luận

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


  • 2
    vominhmanh10  đã bình luận lúc 31, Tháng 10, 2025, 12:23 ← sửa 3

    nếu vẫn cố dùng py thì có các biện pháp sau đây để tối ưu
    chạy chương trình chính bằng hàm, nhanh hơn 5 - 10 lần
    đối với Knapsack sử dụng cắt tỉa loại bỏ các trạng thái vô nghĩa, ví dụ như (5, 10), (6, 9) thì (6, 9) đã giá trị nhỏ hơn mà trọng lượng lại lớn hơn, sẽ không thể tối ưu quy hoạch động nên ta loại bỏ nó

    import sys
def knapsnack_bfs_pruned(n, W, a):
    dp = {0: 0}
    for w, v in a:
        ndp = dp.copy()
        for cw, cv in dp.items():
            nw = cw + w 
            nv = cv + v
            if nw <= W and nv > ndp.get(nw, 0):
                ndp[nw] = nv
        b = sorted(ndp.items())
        c = {}
        max_v = -1
        for cw, cv in b:
            if cv > max_v:
                c[cw] = cv
                max_v = cv
        dp = c
    return max(dp.values())
input = sys.stdin.readline
n, W = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
print(knapsnack_bfs_pruned(n, W, a))

  • 0
    vominhmanh10  đã bình luận lúc 31, Tháng 10, 2025, 11:10 ← sửa 2

    một số bài dùng py mà TLE buộc dùng C++ có 0.013s, vậy py chậm tới 150 lần luôn :((

    #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair< ll, ll>;
#define fi first
#define se second

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, W; cin >> n >> W;
    vector<pll> a(n);
    for (auto &x : a) cin >> x.fi >> x.se;
    vector<ll> dp(W + 1, 0);
    for (ll i = 0; i < n; i++) {
        ll w = a[i].fi, v = a[i].se;
        for (ll j = W; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[W] << "\n";
}

  • 1
    ChiPhatNguyen  đã bình luận lúc 15, Tháng 8, 2025, 16:38

    Quy hoạch động balo mảng 2 chiều

    code vi du: code


  • -7
    LVT_K66_TRANDUYBAO  đã bình luận lúc 26, Tháng 7, 2025, 1:56

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


  • -6
    hahuy0928  đã bình luận lúc 14, Tháng 2, 2025, 2:31 ← sửa 2

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


  • -26
    khiemgia1105  đã bình luận lúc 4, Tháng 10, 2024, 7:48

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


  • -19
    cuyu  đã bình luận lúc 9, Tháng 3, 2024, 1:32 ← sửa 3

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


  • -10
    KIET22  đã bình luận lúc 10, Tháng 9, 2023, 16:07

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


  • -14
    KIET22  đã bình luận lúc 7, Tháng 9, 2023, 13:22

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


  • -9
    teudepdzai  đã bình luận lúc 4, Tháng 9, 2023, 12:44 ← chỉnh sửa

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


    • -6
      hieubecclc01  đã bình luận lúc 9, Tháng 9, 2023, 9:13

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


  • -67
    dang_phuc_hung  đã bình luận lúc 30, Tháng 12, 2021, 15:18

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