Bài toán cái túi
Submit solution
Points:
2
Time limit:
1.0s
Memory limit:
98M
Author:
Problem types
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Cho n đồ vật kích thước là \(a_1,a_2,...,a_n\) và một cái túi có kích thước là \(M\)
Nhiệm vụ của bạn là hãy lựa chọn các đồ vật xếp vào túi cho hợp lý sao cho tổng kích thước được chọn không vượt quá kích thước túi mà nhưng phải lớn nhất có thể
Input
Dòng đầu gồm hai số nguyên dương là số đồ vật \(n (1 \le n \le 20)\) và kích thước túi \(M ((1 \le M \le 1000))\)
Dòng cuối là \(n\) số nguyên dương tương ứng với kích thước các đồ vật có giá trị không vượt quá \(1000\)
Ouput
Một số tự nhiên là kích thước thu được lớn nhất có thể của cái túi, tất nhiên nếu không xếp được đồ vật nào thì xuất ra \(0\)
Ví dụ
Input
4 40
17 26 19 8
Ouput
36
Giải thích Ta chọn 2 đồ vật kích thước là \(17\) và \(19\)có tổng là \(36\)
Comments