مشکل کوله پشتی با بازیابی پاسخ
Problem
با توجه به N موارد جرم m1، …، mN و هزینه c به ترتیب < sub>1، …، cN.
کوله‌پشتی را پر می‌کنند که نمی‌تواند وزنی بیش از M را تحمل کند. مجموعه اقلام قابل حمل در کوله پشتی که بالاترین هزینه را دارد را تعیین کنید.
ورودی:
- سطر اول شامل یک عدد طبیعی N که از 100 تجاوز نمی کند و یک عدد طبیعی M از 10000 تجاوز نمی کند؛
است.
- در خط دوم N اعداد طبیعی mi را وارد کنید که از 100 تجاوز نکند؛
- N اعداد طبیعی باi که بیش از 100 نباشد در خط سوم وارد می شوند.
خروجی: تعداد اقلام (اعداد از 1 تا N) را چاپ کنید که در کوله پشتی با بالاترین هزینه (یک عدد در هر خط) گنجانده می شود. .
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |