Cái túi (Hard version)


Submit solution

Points: 1.80 (partial)
Time limit: 4.0s
Memory limit: 4M

Problem source:
Folklore - Sách thầy Hoàng , mục bài tập tự giải , bài số 1 .
Problem type

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


  • 0
    leduykhongngu  commented on 7, Jun, 2021, 23:32

    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é.


    • 0
      I_love_Hoang_Yen  commented on 8, Jun, 2021, 20:19 edit 5

      Giải thích thêm 1 chút:

      • Mục đích của bài này là giải được với bộ nhớ thấp (4MB)
      • Trên VOJ cũ, do trình chấm chặn memory không chuẩn (1 số submission cũ dùng Pascal có thể hack đc cách đo memory, và 1 số submission mới lại không được chặn mem), nên các "submission mẫu" trên VNOI thực chất đều không AC được bài này.

      <s>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ày</s>

      Edit: bài này đã được thêm test và rejudge