Xếp valy

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type

Một valy có thể chứa tối đa W đơn vị trọng lượng. Có N đồ vật, số lượng mỗi loại không hạn chế. Loại đồ vật thứ i có trọng lượng là Ai và có giá trị là Ci. Hỏi nên chọn những đồ vật nào và số lượng bao nhiêu để xếp vào valy sao cho:

  • Tổng trọng lượng của các đồ vật không vượt quá giới hạn W của valy
  • Tổng giá trị của đồ vật là lớn nhất.

Input:

  • Dòng 1 chứa N và M (1 ≤ N ≤ 40, 1 ≤ M ≤ 100)
  • N dòng tiếp theo, mỗi dòng chứa hai số A[i] và C[i].

Output:

  • Dòng đầu là giá trị lớn nhất
Ví dụ:
INPUT
Copy
4  100
50  50
19  20
80  90
21  25
OUTPUT
Copy
110

Comments

Please read the guidelines before commenting.



  • -6
    khanhdungtrinh  commented 2:05:53 am, 27/09/2023

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