در هکررنگ یک مسئله هست به اسم مسئله‌ی تساوی. اگه بخوام صادق باشم من بیشتر از دو ماهه که تو وقتای بیکاریم دارم با این مسئله سر و کله می‌زنم. در موردش سرچ کردم و راه‌حل‌ها رو دیدم و باز هنوز برام گنگ بود که چرا این مسئله اینطور داره حل میشه. و خب امشب فهمیدم که ماجرا چیه.
مسئله خیلی ساده‌ست. یک آرایه از اعداد داریم که در هر لحظه میشه همه به جز یکی از عناصر رو به اندازه‌ی یکی از مقادیر ۱، ۲ و ۵ افزایش داد. مثلا آرایه‌ی [۱، ۱، ۵] رو میشه با انتخاب عدد ۲ برای افزایش به صورت [۱، ۳، ۷] یا [۳، ۳، ۵] نشون داد. سوال اینه: کمترین مقدار افزایش‌های لازم برای مساوی شدن همه‌ی اعداد آرایه چقدره؟
هدف اینه که این مسئله رو با برنامه‌ریزی پویا حل کنیم. قبل از این کار یک حقه‌ی ساده می‌زنیم. ما می‌خوایم به تساوی برسیم، پس افزایش دادن همه‌ی عناصر به جز عنصر iم به اندازه‌ی k مثل اینه که تنها عنصر iم رو به اندازه‌ی k کاهش بدیم و این کار رو تا زمانی ادامه بدیم که به صفر برسیم. پس تابع هزینه با این توضیح اینطور چیزی میشه:
اینجا wها تعداد دفعاتیه که از ۱، ۲ یا ۵ استفاده می‌کنیم تا بتونیم مقدار عنصر iم رو صفر کنیم یا در واقع با چه ترکیب خطی‌ای میشه عددی که می‌خوایم رو بدست بیاریم. مثلا ۷ رو میشه با ۷تا یک (در صورت مسئله‌ی ما ۷ عملیات) یا یک دونه ۱ و ۳ تا ۲ (۴ عملیات) و یا در نهایت با یدونه ۲ و یدونه ۵ (۲ عملیات) بدست آورد. خب در نهایت کی این تعدادها کمینه میشن؟ وقتی که بزرگترها بار خودشون رو بکشن. یعنی اینطور چیزی:
طبیعتا سه حالت بیشتر به ذهن نمی‌رسه. حالت عنصر ابتدایی، حالتی که مقدار عنصر iم صفر هست و حالتی که نیست. حالتی که صفره که هزینه میشه همون هزینه‌ی قبلی و وقتی نیست میشه هزینه‌ی قبلی + کمینه مقدار عملیات‌ها، یعنی این میشه تابع هزینه‌ی نهایی:
مسئله الان که حل شد چیز زیادی نداره واقعا. تنها در هر مرحله میشه مقدار بهینه‌ی تعداد عملیات بر اساس مقدار عنصر رو به خاطر سپاری کرد و در مراحل بعد استفاده کرد.
Meh.
