#054 · Knapsack Max Value · dp · medium · python
مسئله کوله پشتی
برنامه ای بنویسید که یک ماتریس n * 2 را از ورودی دریافت کند که ستون اول برابر با وزن اشیا و ستون دوم برابر با ارزش آنها خواهد بود. بعد با توجه به وزن کوله که داده خواهد شد، بیشترین تعداد آیتمی که میتوان در کوله جای داد تا ارزش کلی آنها بیشترین مقدار باشد را خروجی دهید.
ورودی:
- در خط اول ورودی به شما ظرفیت کوله داده میشود.
- در خط دوم ورودی n که تعداد سطر های ماتریس است داده میشود.
- در n خط بعدی در مقدار اول وزن شی و در مقدار دوم ارزش آن داده میشود که با فاصله از هم جدا شده اند.
خروجی:
- در خط اول خروجی بیشترین تعداد آیتمی که میتوانیم در کوله جای دهیم را چاپ کنید.
- در یک ماتریس n * 2 در ستون اول شماره شی و در ستون دوم اگر استفاده شده بود مقدار 1 و در غیر این صورت 0 را چاپ کنید.
Input Test:
5
4
5 60
3 50
4 70
2 30
OutPut Test:
2
1 0
2 1
3 0
4 1