BCCOW spoj PTIT – Đi xem phim

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCCOW/

1. Đề bài BCCOW spoj PTIT

Nông dân John đang đưa các con bò của anh ta đi xem phim! Xe tải của anh ta thì có sức chứa có hạn thôi, là C (100 <= C <= 5000) kg,

anh ta muốn đưa 1 số con bò đi xem phim sao cho tổng khối lượng của đống bò này là lớn nhất, đồng thời xe tải của anh ta vẫn chịu được.

Cho N (1 <= N <= 16) con bò và khối lượng W_i của từng con, hãy cho biết khối lượng bò lớn nhất mà John có thể đưa đi xem phim là bao nhiêu.

Dữ liệu

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: C và N
  • Dòng 2..N+1: Dòng i+1 chứa 1 số nguyên: W_i

Kết quả

  • Dòng 1: Một số nguyên là tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim.

Ví dụ:

Dữ liệu:

259 5

81

58

42

33

61

Kết quả:

242

Giải thích: 81+58+42+61 = 242; đây là tổng khối lượng bò lớn nhất có thể được.

2. Hướng dẫn BCCOW spoj PTIT

– bài này các bạn có thể dùng tham lam.

3. code tham khảo BCCOW spoj PTIT

2 thoughts on “BCCOW spoj PTIT – Đi xem phim

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *