Atcoder Educational DP Contest D - Knapsack 1

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
NoobCpp
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
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~.

Comments

Please read the guidelines before commenting.


  • 2
    vominhmanh10  commented on Oct. 31, 2025, 12:23 p.m. ← edit 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  commented on Oct. 31, 2025, 11:10 a.m. ← edit 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  commented on Aug. 15, 2025, 4:38 p.m.

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

    code vi du: code


  • -10
    LVT_K66_TRANDUYBAO  commented on July 26, 2025, 1:56 a.m.

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


  • -6
    hahuy0928  commented on Feb. 14, 2025, 2:31 a.m. ← edit 2

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


  • -28
    khiemgia1105  commented on Oct. 4, 2024, 7:48 a.m.

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


  • -21
    cuyu  commented on March 9, 2024, 1:32 a.m. ← edit 3

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


  • -10
    KIET22  commented on Sept. 10, 2023, 4:07 p.m.

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


  • -15
    KIET22  commented on Sept. 7, 2023, 1:22 p.m.

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


  • -10
    teudepdzai  commented on Sept. 4, 2023, 12:44 p.m. ← edited

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


    • -6
      hieubecclc01  commented on Sept. 9, 2023, 9:13 a.m.

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


  • -70
    dang_phuc_hung  commented on Dec. 30, 2021, 3:18 p.m.

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