Submit solution
Points:
1.80 (partial)
Time limit:
4.0s
Memory limit:
4M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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
Comments
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