Đi xem phim
Xem dạng PDF
Gửi bài giải
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Điểm:
0,05 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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 \le C \le 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 \le N \le 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.
Input
- 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~
Output
- 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.
Sample Input
259 5
81
58
42
33
61
Sample Output
242
Note
~81 + 58 + 42 + 61 = 242~; đây là tổng khối lượng bò lớn nhất có thể được.
Bình luận
n<=20đệ quy tốtBình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
hint: binary search
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.