Bài toán ba lô dạng 1 (Mỗi đồ vật chỉ được chọn tối đa 1 lần)

Cho n đồ vật, mỗi đồ vật i có:

• trọng lượng wi
• giá trị vi

Một ba lô có sức chứa tối đa W

Yêu cầu:

• Tìm cách chọn các đồ vật sao cho:
  • Tổng trọng lượng ≤W
  • Tổng giá trị là lớn nhất
• In ra:
  • Tổng giá trị V
  • Danh sách các đồ vật được chọn

Dữ liệu vào test.inp dạng:

n W
w1 v1
w2 v2
...
wn vn

Dữ liệu ra test.out dạng:

<tổng giá trị> | <danh sách đồ vật>