trang chủ / đề bài / knapflip

Ba Lô Đảo Chiều DP

Đề bài

Mô tả

Cho N vật. Vật thứ i có khối lượng wi và giá trị vi. Bạn có một ba lô sức chứa W (có thể rất lớn).

Mỗi vật chỉ được chọn tối đa 1 lần. Hãy tìm tổng giá trị lớn nhất đạt được sao cho tổng khối lượng không vượt W.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và W.
  • N dòng tiếp theo, mỗi dòng chứa hai số nguyên wi và vi.

Dữ liệu ra

In ra một số nguyên: tổng giá trị lớn nhất.

Ràng buộc

  • 1≤N≤100
  • 1≤W≤109
  • 1≤wi≤109
  • 1≤vi≤50 (tổng ∑vi≤5000)

Ví dụ

Input Output Giải thích
3 10
5 6
4 5
3 4		 11 Chọn vật 1 và 2: khối lượng 9, giá trị 11.
4 1000000000
100 10
200 20
300 30
400 40		 100 Tổng khối lượng 1000 rất nhỏ so với W, nên lấy cả 4 vật. Tổng giá trị 100.

Ghi chú

  • W rất lớn nhưng ∑vi nhỏ. DP theo giá trị thay vì theo khối lượng.

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.402 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.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0