الگوریتم کوله‌پشتی، یک الگوریتم از نوع حریصانه هست. در این مطلب در مورد الگوریتم کوله‌پشتی یک و صفر (0/1 knapsack algorithm) می‌نویسم. برای مثال فرض کنید یک کوله پشتی با حجم ۹۰ لیتر دارید؛ و وسایلی که دارید علاوه بر حجم برای شما یک ارزش یا اهمیت دارند و احتمالا همه آن‌ها جا نمی‌شوند. حال به چه صورت وسایل را انتخاب می‌کنید تا بیشترین ارزش را در کوله پشتی خود داشته باشید؟ در الگوریتم کوله‌پشتی یک و صفر یا یک شی انتخاب می‌شود و یا خیر! امکان برش و تکه کردن نیست.
این الگوریتم به این شکل است که شما ابتدا اشیا را بر حسب نسبت ارزش به حجم (\frac{ارزش} {حجم}) مرتب می‌کنید و سپس از اولین مورد شروع به انتخاب می‌کنید؛ اگر جا شد آن را در کیف می‌گذارید و به سراغ بعدی می‌روید. نمونه کد زیر پیاده‌سازی این الگوریتم رو با استفاده از dataclass برای هر آیتم در پایتون نشون می‌دهد:
from dataclasses import dataclass
@dataclass
class Item:
value: float
size: float
@property
def ratio(self):
return self.value / self.size
def choose(items: list[Item], size: float) -> tuple[list[Item], float]:
items.sort(key=lambda i: i.ratio)
chosen: list[Item] = []
value = 0.0
for item in items:
if item.size <= size:
chosen.append(item)
size -= item.size
value += item.value
if size == 0:
break
return chosen, value
ضعف الگوریتم کوله‌پشتی (حریصانه)
البته الگوریتم‌های حریصانه (Greedy) مانند همین الگوریتم کوله پشتی هیچ تضمینی برای بهترین انتخاب نمی‌دهند. این الگوریتم با هزینه زمانی خوبی می‌تونه چنین مسئله هایی رو حل کند ولی همیشه بهترین جواب را نمی‌دهد و باید این را در نظر داشته باشید. برای مثال فرض کنید فهرست چیزهایی که می‌خواهیم در سفر و در کوله داشته باشیم به شکل زیر هست:
| شی | ارزش | حجم | نسبت |
| گاز تک‌شعله | ۵۰ | ۴۰ | ۱٬۲۵ |
| پتو | ۱۰۰ | ۸۰ | ۱٬۲۵ |
| چای | ۲۰ | ۱۵ | ۱٬۳۳ |
| طناب | ۲۶ | ۱۹٬۵ | ۱٬۳۳ |
مشکل اینجاست که الگوریتم کوله پشتی بر اساس نسبت ارزش به حجم (\frac{ارزش} {حجم}) کار می‌کند و نه ارزش واقعی. در مثال بالا ارزش «گاز تک‌شعله» و «پتو» برابر شده حالا اگر کوله ما مثلا با حجم ۱۰۰ باشه انتخاب های الگوریتم (احتمالا) میشه «گاز و چای» که مجموع ارزش میشه ۵۰+۲۰=۷۰ در حالی که انتخاب منطقی‌تر «پتو و طناب» هست که مجموع ارزش‌شون ۱۰۰+۲۶=۱۲۶ میشه.
این ضعف الگوریتم کوله‌پشتی و کلا الگوریتم های حریصانه هست و هرچند که میشه بعضی مشکلات رو گاهاً با تکنیک ها و ترفند ها حل کرد، اما همیشه حالتی هست که جواب بهینه رو نمیده.
درواقع برای این که یک راه حل داشته باشیم که حتما تمام حالات رو بررسی کنه و بهترین جواب رو بده باید تمام ترکیب های ممکنه رو بررسی کنیم تا به جواب بهینه برسیم. این یعنی تمام زیر مجموعه‌ها رو درنظر بگیرید و ارزش رو محاسبه کنید. هزینه زمانی چنین الگوریتم از مرتبه O(n^2) هست.
