طراحی الگوریتم کوله پشتی
چهار سال پیش منتشر شده
تعداد بازدید: 521
کد پروژه: 312156
شرح پروژه
در یک ردیف n کیسه وجود دارد که در بعضی از آنها یک سکه طلا هست و در بعضی هم یک سکه نقره است. شما اجازه دارید که تعدادی کیسه ی متوالی با سکه طلا را برای خودتان بردارید و سکه ها را صاحب شوید. منطقاً شما باید به دنبال بزرگترین زیر رشته (تعدادی کیسه متوالی) در این ردیف باشید که در همه ی آنها طلا باشد تا تعداد سکه بیشتری گیرتان بیاید.
فرض کنید که شما یک چوب جادو هم دارید که اگر آن را به یک کیسه حاوی سکه نقره بزنید، آن سکه نقره را به طلا تبدیل کند (مسلماً چوب جادو اثرث روی کیسه های با سکه طلا ندارد). اما از این چوب جادو حداکثر میتوانید k بار استفاده کنید و بعد از آن خاصیتش را از دست میدهد.
از آنجایی که شما میخواهید حداکثر سکه ی طلای ممکن را برای خودتان بردارید، باید طوری از قدرت این چوب جادو استفاده کنید که طول بزرگترین زیر رشته از کیسه های طلا حداکثر شود.
با روش برنامه نویسی پویا برنامه ای بنویسید که حداکثر سکه ی طلای ممکن را به دست آورید.
شکل زیر یک نمونه از این مسئله را نشان میدهد.
ورودیدر خط اول ورودی nn که تعداد کیسه ها است به همراه kk تعداد دفعه مجاز استفاده از چوب جادو داده میشود (k \le n \le 10000k≤n≤10000).
در خط دوم یک رشته به طول nn داده می شود که شامل نوع سکه در کیسه ها است. در این رشته، GG به معنای سکه طلا و SS به معنای نقره است.
خروجیطول طولانی ترین زیررشته از کیسه های حاوی سکه ی طلا (حداکثر سکه طلای قابل برداشتن)
مثالدر اینجا چند نمونه برای فهم بهتر صورت سوال و قالب ورودی و خروجی تستها داده میشود.
ورودی نمونه ۱8 2
GSGSSGGS
Copy
خروجی نمونه ۱
5
Copy
مهارت ها و تخصص های مورد نیاز
مبلغ پروژه
100,000 تومان
مهلت برای انجام
4روز
وضعیت مناقصه
انجام شده
درباره کارفرما
عضویت شش سال پیش
