Bài toán ba lô 2

Xem PDF
Thời gian:
Python 3 5.0s
Bộ nhớ:
Python 3 640M
Tác giả:
jumptozero
Dạng bài
Điểm: 400 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

  • Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^9)\)

  • \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^3)\)

Output

  • In ra giá trị cần tìm.

Example

Test 1

Input 
3 8
3 30
4 50
5 60
Output 
90
Note

Giải thích: Viên bi thứ \(1\) và \(3\) sẽ được chọn để bỏ vào ba lô. Vì chúng có tổng khối lượng không quá \(8\) và có giá trị lớn nhất là \(90\).

Bình luận


  • 1
    Hikarii    3:52 p.m. 23 Tháng 8, 2020 ← chỉnh sửa 4

    Trả lời câu hỏi từ \(\(anh hai SPyofgame\)\) editorial:

    • Nhận thấy rằng max v[i] = 10^3 và max n = 100, tổng giá trị lớn nhất có thể nhận được là max sum = (max n) * (max v[i]) = 10^5
    • Gọi dp[sum] = weight (giả sử chọn được các món đồ có tổng giá trị (không phải tổng cân nặng như trong bài KNAPSACK1) là sum, thì cần chiếc túi có sức chứa tối thiểu là weight)
    • Vậy, đáp án sẽ là một sum nào đó, miễn là dp[sum] <= W
    • Sẽ có rất nhiều giá trị sum thỏa mãn điều trên, nên ta sẽ chọn sum lớn nhất
    • Kết luận, ta sẽ đưa lại được bài này về Knapsack bình thường, với bộ nhớ O(max sum)

    \(\(Preference\)\) Reference AC code: https://ideone.com/UvVwLB


    • 0
      SPyofgame    4:51 p.m. 23 Tháng 8, 2020

      Thực tế code bạn có độ phức tạp \(O(sum + n)\) bộ nhớ đấy. Bạn có thể giải trực tiếp bài này ngay khi vừa nhận cặp số \((weight_i, value_i)\) chứ 😃


      • 0
        Hikarii    4:55 p.m. 23 Tháng 8, 2020

        em chưa nghĩ ra cách giải online ;-; anh hai em mạnh quá orz


        • 0
          SPyofgame    5:10 p.m. 23 Tháng 8, 2020

          Bạn rank cam lqdoj trình gần Expert codeforces rồi orz cái gì ở đây ._.

      2 bình luận nữa