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:
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
    cuyu  đã bình luận lúc 9, Tháng 3, 2024, 1:32 sửa 2

    QHD


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

    nên cài thêm test bài


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

    cài thêm test đi NoobCpp a


  • -2
    teudepdzai  đã bình luận lúc 4, Tháng 9, 2023, 12:44

    em khá gà mờ nên không biết dùng quy hoạch động, mng xem hộ em tại sao em bị sai test 6 tới 13 ạ, ai biết chỉ em với

    include <bits/stdc++.h>

    using namespace std;

    int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); unsigned long long n,u,w[10000],c[10000],t=0; cin>>n>>u; for(int i=1;i<=n;i++)cin>>w[i]>>c[i];

    for(int i=1;i<=n;i++)
       for(int j=i+1;j<=n;j++)
       if(c[i]&lt;c[j])
       {
           swap(c[i],c[j]);
           swap(w[i],w[j]);
       }
    
    
       for(int i=1;i<=n;i++)
           if(w[i]<=u)
          {
              t=t+c[i];
              u=u-w[i];
          }
    
        cout<&lt;t<<endl;
        return 0;
    

    }


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

      Bài này bạn nên dùng quy hoạch động cái túi để làm nhé.


  • -36
    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.