کوله پشتی ۹۸

سلام، قصد دارم در مورد کوله پشتی بنویسم، کوله پشتی کارهایی که قرار هست در سال جدید انجام بدیم ولی می‌خواهم یک مقدار متفاوت‌تر بنویسم.

با خودم گفتم نوشتن یک مطلب که من قرار است چه کارهایی انجام بدم شاید خیلی برای دیگران هیجان‌انگیز نباشد پس تصمیم گرفتم گریزی بزنم به مسئله معروف کوله پشتی(یا Knapsack).

داستان از این قراره که شما یک کوله پشتی با ظرفیت محدود دارید و تعدادی شئ با اندازه‌های متفاوت و قیمت‌های متفاوت در اختیار دارید که می‌خواهید کوله پشتی خود را پر کنید، طبیعتاً حالتی مطلوب است که بیش‌ترین ارزش را در کوله پشتی جا دهید.

این مسئله انواع گوناگونی دارد که مثلا می توانید یک شئ را نصف کنید و بردارید با نصف ارزش ولی مدل ساده‌ی آن مدل باینری(صفر یا یک) است که فقط می توانید کل یک شئ را بردارید یا اصلاً برندارید.

راه حل ریاضی این مسئله با الگوریتم‌های dynamic programming است که کاری به جزیّیات آن ندارم ولی بیایید همین مثال را در کوله پشتی ۹۸ خود به کار ببریم: ما زمان محدودی داریم که باید به بهترین نحو از آن استفاده کنیم(البته با این فرض که قرار است از زمان درست استفاده کنیم.) و هر کاری را یا باید کامل انجام دهیم یا اصلاً انجام ندهیم چون کار نصفه نیمه بدون ارزش است و فقط منابع ما را هدر می‌دهد بدون اینکه دستاوردی داشته باشد :)

توجه داریم که اولویت‌ها(یا ارزش شئ‌ها) برای هر کس متفاوت است و لزومی ندارد همه کوله پشتی یکسانی داشته‌باشیم، اصلاً برای همین است در همین ویرگول تعدادی آدم کوله‌پشتی های خودشون را برای ما تشریح کردند.

شاد باشید و خندون، مثل همیشه با نظراتتون به این مطلب ارزش بدید.