THUHOACH - Thu hoạch vụ mùa
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Hiện đang vào mùa thu hoạch ngô, nhà Tí có một chiếc công nông tải trọng có hạn, chỉ chở được tối đa ~C~ (kg), trong khi đó nhà Tí lại thu được ~N~ bao ngô, bao thứ ~i~ có khối lượng là ~w_i~ (kg), hãy giúp Tí tính xem một chuyến xe nhà Tí có thể chở được khối lượng ngô tối đa là bao nhiêu?
Input
- Dòng đầu chứa hai số nguyên dương ~N,C~;
- Dòng thứ hai chứa ~N~ số nguyên dương ~w_1, w_2, …, w_N~, mỗi số cách nhau bởi một dấu cách.
Giới hạn:
- ~1 ≤ N ≤ 20, 1 ≤ C, w_i ≤ 50000~.
Output
- Một số nguyên duy nhất là khối lượng ngô tối đa xe nhà tí chở được trong một chuyến.
Sample
Input #1
5 259
81 58 42 33 61
Output #1
242
Hint
Giải thích #1:
- Chở các bao ngô số ~1, 2, 3, 5~ ta có tổng khối lượng là: ~81+58+42+61 = 242~, đây là tổng khối lượng ngô lớn nhất có thể chở được.
Problem source: Chuyên Sơn La Online Judge
Bình luận
mấy bn python cho mình xin code với
test 5 6 là gì v ạ
Ý tưởng là dùng quay lui tìm tất cả tổng max của số bao ngô có thể chọn từ 0 đến n; sau đó lấy một mảng khác hứng kết quả các tổng max đó; sau đó so sánh kết quả trong tổng max đó với trọng tải của xe để ra được số kg ngô lớn nhất có thể chở.
ủa bài quy hoạch động mà mình cài quay lui cũng ac này =))
do N<=20 ak chứ mà N<=10^6 là xong đáy:)
ai cho mình xin í tưởng đc ko bí quá :v
dùng quy hoạch động nha
test case 5 là gì vậy ạ