Atcoder Educational DP Contest E - Knapsack 2

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^9)~: 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^3)~ 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
1 1000000000
1000000000 10
Output
10

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.


  • -4
    vominhmanh10  đã bình luận lúc 31, Tháng 10, 2025, 13:23 ← chỉnh sửa

    tại dp khi xét các w,v với wj >= wi mà vj <= vi, wj => vj,wj ko đóng góp tối ưu bài toán nên ta cần loại các trạng thái dp này
    kĩ thuật bfs_knapsnack sẽ giúp loại bỏ các trạng thái dư thừa đó
    do pha sắp sếp tốn O(n log n) nên dùng khi n nhỏ như bài này còn không dp theo giá trị như ngta:))

    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))

  • 1
    usingnamespacestd  đã bình luận lúc 11, Tháng 10, 2024, 1:03

    value = 1e5


  • 6
    vuthinh1072008  đã bình luận lúc 21, Tháng 7, 2024, 17:28 ← chỉnh sửa

    code quy hoạch động 2 chiều

    https://ideone.com/EQwRS9


  • 5
    Nguyen_le2632007  đã bình luận lúc 22, Tháng 5, 2024, 12:37

    bản chất bài này thì thay vì dùng index và khối lượng để để làm trạng thái thì ta dùng index và giá trị một cách solution dễ đọc dễ hiểu 

    #include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define ll long long

ll n, w, a[100009], b[100009];
ll dp[109][100009];

// map&lt;int, map&lt;ll, ll> > dp;

ll dfs(int k, int idx) {
    if (idx == n)
        return (k == 0) ? 0 : INT_MAX;

    if (dp[idx][k] != -1)
        return dp[idx][k];

    if (b[idx] <= k)
        return dp[idx][k] = min(dfs(k, idx + 1), a[idx] + dfs(k - b[idx], idx + 1));
}

int s(int v_max, int min_n) {
    for (int i = v_max; i >= min_n; i--) {
        if (dfs(i, 0) <= w)
            return i;
    }
    return 0;
}

int main() {

    cin >> n >> w;
    memset(dp, -1, sizeof(dp));

    int v_max = 0;
    ll v_min = (int)1e9;

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        v_max += b[i];
        v_min = min(v_min, b[i]);
    }

    cout << s(v_max, v_min) << endl;
}

  • 2
    RussVN123  đã bình luận lúc 17, Tháng 3, 2024, 9:56

    Chắc có mình tui là code mảng 2 chiều :V


    • 1
      melondepchai  đã bình luận lúc 19, Tháng 6, 2024, 16:02

      DP như nào vậy ông, tôi làm mãi không xong


      • 5
        RussVN123  đã bình luận lúc 20, Tháng 6, 2024, 4:33 ← chỉnh sửa

        Spoil nha ông

        ! Thay vì dp[i][j] là giá trị lớn nhất khi xét i vật và khối lượng là j thì mình sẽ đổi thành khối lượng bé nhất khi xét i vật và giá trị là j ( vì giá trị bài này bé ) . Từ đây thì tìm j lớn nhất sao cho f[n][j] <=W thôi ông. Ông có thể xem solution để rõ hơn :VVV


        • 3
          melondepchai  đã bình luận lúc 7, Tháng 7, 2024, 9:38

          à ổn r, tks ông nha


  • -16
    phongngutin  đã bình luận lúc 12, Tháng 12, 2023, 13:06 ← 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.


  • -27
    duonggiabao2008  đã bình luận lúc 12, Tháng 12, 2023, 13:04 ← 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.


  • -27
    Bui_Quoc_Cuong  đã bình luận lúc 12, Tháng 12, 2023, 13:01

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


  • 2
    beater24  đã bình luận lúc 20, Tháng 8, 2023, 3:36

    Đề tuy không khó nhưng phải tối ưu được thời gian tốt


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

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


  • 13
    canhtoanle  đã bình luận lúc 16, Tháng 5, 2022, 8:46

    Đề rất hay và bổ ích