trang chủ / bài tập / halfknap

Ba lô nửa đầy

Đề bài

Mô tả

Bạn có một chiếc ba lô sức chứa Wn món đồ, món thứ i nặng wi.

Hãy chọn một số món bỏ vào ba lô sao cho tổng trọng lượng C của chúng ít nhất bằng một nửa sức chứa nhưng không vượt quá sức chứa, tức là:

W2CW

Lưu ý bạn không cần làm tổng trọng lượng lớn nhất có thể, chỉ cần nó nằm trong đoạn trên. Nếu có nhiều cách chọn thoả mãn, in ra cách nào cũng được. Nếu không tồn tại cách chọn nào, hãy báo là không thể.

Dữ liệu vào

  • Dòng đầu chứa số nguyên t: số lượng bộ dữ liệu.
  • Với mỗi bộ dữ liệu:
    • Dòng đầu chứa hai số nguyên nW.
    • Dòng thứ hai chứa n số nguyên w1,w2,,wn.

Dữ liệu ra

Với mỗi bộ dữ liệu:

  • Nếu không có cách chọn nào thoả mãn, in ra một số 1.
  • Ngược lại, in ra trên dòng đầu số lượng món m được chọn, dòng thứ hai in m số nguyên đôi một khác nhau j1,j2,,jm (1jin) là chỉ số các món được chọn.

Ràng buộc

  • 1t104
  • 1n2·105
  • 1W1018
  • 1wi109
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 2·105.

Ví dụ

Input Output Giải thích
3
1 3
3
6 2
19 8 19 69 9 4
7 12
1 1 1 17 1 1 1
1
1
-1
6
1 2 3 5 6 7
Bộ 1: món duy nhất nặng đúng 3=W. Bộ 2: W=2 nhưng mọi món đều nặng hơn 2 nên không bỏ được món nào. Bộ 3: 12/2=6, lấy sáu món nặng 1 (bỏ qua món nặng 17) cho tổng đúng 6.
4
2 10
1000000000 6
3 10
11 3 3
1 5
2
2 9
4 4
1
2
2
2 3
-1
2
1 2
Bộ 1: món 1 nặng hơn W nên phải bỏ qua, món 2 nặng 6[5,10]. Bộ 2: món 1 nặng 11>10, hai món còn lại cho tổng 6. Bộ 3: 5/2=3 mà món duy nhất chỉ nặng 2. Bộ 4: 9/2=5 nên một món nặng 4 là chưa đủ, phải lấy cả hai để được 8.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0