کوله پشتی 0-1: بیشترین وزن
Problem
با توجه به N شمشهای طلا به جرم m1، …، mN. آنها یک کوله پشتی را پر می کنند که نمی تواند وزنی بیش از M را تحمل کند. بیشترین مقدار طلایی که می توان در چنین کوله پشتی حمل کرد چقدر است؟
ورودی:
- خط اول شامل یک عدد طبیعی N بیش از 100 و یک عدد طبیعی M بیش از 10000 نیست؛
- خط دوم حاوی N اعداد طبیعی mi است که از 100 تجاوز نمی کنند.
خروجی: چاپ یک عدد صحیح - بیشترین مقدار طلای ممکن که می توان در کوله پشتی داده شده حمل کرد.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
2 3195
38 41
|
79 |