Xếp valy

View as PDF
Submit solution
Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout
Author:
kieulqd
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à ~A_i~ và có giá trị là ~C_i~. 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
4  100
50  50
19  20
80  90
21  25
OUTPUT
110

Comments

Please read the guidelines before commenting.


  • -6
    khanhdungtrinh  commented on Sept. 27, 2023, 2:05 a.m.

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