Cái túi (Hard version)
Xem dạng PDF
Gửi bài giải
Điểm:
1,80 (OI)
Giới hạn thời gian:
4.0s
Giới hạn bộ nhớ:
4M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho ~N~ đồ vật, vật ~i~ có khối lượng ~W_i~ và giá trị là ~V_i~. Một cái túi có thể chịu được khối lượng tối đa là ~M~, quá thì sẽ rách. Hãy tìm cách nhét ~1~ số đồ vật vào trong túi sao cho túi không bị rách và tổng giá trị của các đồ vật nhét vào là lớn nhất.
Chú ý:
- Bài này Time limit trên vn.spoj.com bị đặt quá nhỏ (lý do là khi máy chấm SPOJ cập nhật lên máy Cube đã tự động chỉnh time limit xuống ~0.1s~ - quá nhỏ).
- Trên VNOJ, mình để giới hạn bộ nhớ là ~4~MB và giới hạn thời gian là ~4s~.
Input
Dòng đầu tiên là số nguyên ~T~ là số bộ test. ~(1 \leq T \leq 40)~
Mỗi bộ test sẽ có format như sau:
Dòng ~1~: ~2~ số nguyên dương ~N~, ~M~ ~(1 \leq N \leq 10000~, ~1 \leq M \leq 1000)~.
Dòng ~2~: Gồm ~N~ số nguyên là ~W_i~ ~(1 \leq W_i \leq 1000)~.
Dòng ~3~: Gồm ~N~ số nguyên là ~V_i~ ~(1 \leq V_i \leq 10000)~.
Output
Với mỗi bộ test:
Dòng đầu tiên ghi ra giá trị lớn nhất có thể đạt được và số ~K~ là số đồ vật lựa chọn.
Dòng thứ ~2~ ghi ra chỉ số của ~K~ đồ vật được chọn.
Sample Input
1
3 4
1 2 3
4 5 6
Sample Output
10 2
1 3
Bình luận
bài này khó vậy, làm toàn tràn bộ nhớ mà chả biết làm sao :v. làm theo cách thông thường thì bộ nhớ lên đến 40 MB, ai đó giúp giải bài này với :(
giới hạn time, memory vừa đủ luôn, bópp thế
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
cho mình hỏi trường hợp ko chọn đc cái nào thì output sao thế ạ
Các bạn chú ý bài này có Memory limit rất thấp (4MB), có thể các code mẫu cũ ở các nền tảng khác sẽ không AC được. Và các bạn cũng có thể bị lỗi RTE nếu dùng quá bộ nhớ nhé.
Giải thích thêm 1 chút:
Bài này mình đã kiểm tra khá kĩ, vẫn có ít nhất 2 (!!) cách khác nhau có thể AC bài nàyEdit: bài này đã được thêm test và rejudge