کوله پشتی 0-1: حداقل اقلام
Problem
با توجه به N موارد جرم m1، …، mN. آنها یک کوله پشتی را پر می کنند که نمی تواند وزنی بیش از M را تحمل کند. چگونه می توان دقیقاً در M با استفاده از حداقل موارد ممکن وزن اضافه کرد؟
ورودی:
- خط اول شامل یک عدد طبیعی N که از 100 تجاوز نمی کند و یک عدد طبیعی M که از 10000 تجاوز نمی کند، می باشد.
- خط دوم حاوی N اعداد طبیعی mi است که از 100 تجاوز نمی کنند.
خروجی: کمترین تعداد مورد نیاز خود را چاپ کنید، یا اگر نمیتوانید به وزن معین برسید، 0 را چاپ کنید.
نمونهها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
1 5968
18
|
0 |