Cái túi (Hard version)

View as PDF

Submit solution

Points: 1.80 (partial)
Time limit: 4.0s
Memory limit: 4M
Input: stdin
Output: stdout

Problem source:
Folklore - Sách thầy Hoàng , mục bài tập tự giải , bài số 1 .
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.



  • 0
    nguyenhungphongg  commented on March 29, 2024, 10:19 a.m.

    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 :(


  • -4
    Winboy423minhkhoi  commented on Aug. 25, 2023, 12:19 p.m.

    giới hạn time, memory vừa đủ luôn, bópp thế


  • -7
    HTPhuoc  commented on Aug. 10, 2023, 2:32 p.m. edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 4
    cbl_nhat  commented on Dec. 24, 2021, 9:07 a.m.

    cho mình hỏi trường hợp ko chọn đc cái nào thì output sao thế ạ


  • 4
    leduykhongngu  commented on June 7, 2021, 4:32 p.m.

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


    • 1
      I_love_Hoang_Yen  commented on June 8, 2021, 1:19 p.m. edit 6

      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.

      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

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