پرش به محتویات

مسئله کوله‌پشتی

پیش‌نیاز: مقدمه‌ای بر برنامه‌نویسی پویا

مقدمه

مثال زیر را در نظر بگیرید:

[USACO07 Dec] Charm Bracelet

$n$ آیتم مجزا و یک کوله‌پشتی با ظرفیت $W$ وجود دارد. هر آیتم ۲ ویژگی دارد: وزن ($w_{i}$) و ارزش ($v_{i}$). شما باید زیرمجموعه‌ای از آیتم‌ها را برای قرار دادن در کوله‌پشتی انتخاب کنید به طوری که وزن کل از ظرفیت $W$ بیشتر نشود و ارزش کل بیشینه گردد.

در مثال بالا، هر آیتم تنها دو حالت ممکن دارد (برداشته شود یا نشود)، که متناظر با مقادیر باینری ۰ و ۱ است. به همین دلیل، این نوع مسئله «مسئله کوله‌پشتی ۰-۱» نامیده می‌شود.

کوله‌پشتی ۰-۱

توضیح

در مثال بالا، ورودی‌های مسئله به شرح زیر است: وزن آیتم $i$-ام $w_{i}$، ارزش آیتم $i$-ام $v_{i}$ و ظرفیت کل کوله‌پشتی $W$.

فرض کنید $f_{i, j}$ حالت برنامه‌نویسی پویا باشد که نشان‌دهنده بیشترین ارزش کلی است که کوله‌پشتی با ظرفیت $j$ می‌تواند حمل کند، در حالی که تنها $i$ آیتم اول در نظر گرفته شده‌اند.

با فرض اینکه تمام حالت‌های مربوط به $i-1$ آیتم اول پردازش شده‌اند، برای آیتم $i$-ام چه گزینه‌هایی وجود دارد؟

  • وقتی در کوله‌پشتی قرار داده نمی‌شود، ظرفیت باقیمانده بدون تغییر باقی می‌ماند و ارزش کل نیز تغییر نمی‌کند. بنابراین، بیشترین ارزش در این حالت $f_{i-1, j}$ است.
  • وقتی در کوله‌پشتی قرار داده می‌شود، ظرفیت باقیمانده به اندازه $w_{i}$ کاهش و ارزش کل به اندازه $v_{i}$ افزایش می‌یابد، بنابراین بیشترین ارزش در این حالت $f_{i-1, j-w_i} + v_i$ است.

از این رو می‌توانیم معادله انتقال DP را استخراج کنیم:

$$f_{i, j} = \max(f_{i-1, j}, f_{i-1, j-w_i} + v_i)$$

علاوه بر این، از آنجا که $f_{i}$ تنها به $f_{i-1}$ وابسته است، می‌توانیم بعد اول را حذف کنیم. به این ترتیب به رابطه انتقال زیر می‌رسیم:

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

که باید به ترتیب نزولی $j$ اجرا شود (تا $f_{j-w_i}$ به طور ضمنی به $f_{i-1,j-w_i}$ اشاره کند و نه $f_{i,j-w_i}$).

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

پیاده‌سازی

الگوریتم توصیف‌شده را می‌توان با پیچیدگی زمانی $O(nW)$ به صورت زیر پیاده‌سازی کرد:

for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

مجدداً به ترتیب اجرا توجه کنید. این ترتیب باید به دقت رعایت شود تا این شرط ثابت تضمین گردد: درست قبل از پردازش زوج $(i, j)$، مقدار $f_k$ برای $k > j$ متناظر با $f_{i,k}$ است، اما برای $k < j$ متناظر با $f_{i-1,k}$ است. این امر تضمین می‌کند که مقدار $f_{j-w_i}$ از مرحله $(i-1)$-ام گرفته می‌شود، نه از مرحله $i$-ام.

کوله‌پشتی کامل

مدل کوله‌پشتی کامل شبیه به کوله‌پشتی ۰-۱ است، با این تفاوت که در اینجا هر آیتم می‌تواند به تعداد نامحدود انتخاب شود، نه فقط یک بار.

می‌توانیم با الهام از ایده کوله‌پشتی ۰-۱، حالت را تعریف کنیم: $f_{i, j}$، بیشترین ارزشی که کوله‌پشتی با ظرفیت حداکثر $j$ می‌تواند با استفاده از $i$ آیتم اول به دست آورد.

باید توجه داشت که اگرچه تعریف حالت مشابه کوله‌پشتی ۰-۱ است، اما رابطه انتقال آن با کوله‌پشتی ۰-۱ متفاوت است.

توضیح

رویکرد ساده این است که برای $i$ آیتم اول، تعداد دفعات برداشتن هر آیتم را شمارش کنیم. پیچیدگی زمانی این روش $O(n^2W)$ است.

این روش به معادله انتقال زیر منجر می‌شود:

$$f_{i, j} = \max\limits_{k=0}^{\infty}(f_{i-1, j-k\cdot w_i} + k\cdot v_i)$$

همزمان، این رابطه به یک معادله «مسطح» ساده‌تر تبدیل می‌شود:

$$f_{i, j} = \max(f_{i-1, j},f_{i, j-w_i} + v_i)$$

دلیل کارکرد این رابطه این است که $f_{i, j-w_i}$ خود قبلاً توسط $f_{i, j-2\cdot w_i}$ و به همین ترتیب به‌روزرسانی شده است.

مشابه کوله‌پشتی ۰-۱، می‌توانیم برای بهینه‌سازی پیچیدگی فضا، بعد اول را حذف کنیم. این کار همان رابطه انتقال کوله‌پشتی ۰-۱ را به ما می‌دهد.

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

پیاده‌سازی

الگوریتم توصیف‌شده را می‌توان با پیچیدگی زمانی $O(nW)$ به صورت زیر پیاده‌سازی کرد:

for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

با وجود داشتن رابطه انتقال یکسان، کد بالا برای کوله‌پشتی ۰-۱ نادرست است.

با مشاهده دقیق کد، می‌بینیم که برای آیتم $i$ که در حال پردازش است و حالت فعلی $f_{i,j}$، زمانی که $j\geqslant w_{i}$ باشد، $f_{i,j}$ تحت تأثیر $f_{i,j-w_{i}}$ قرار می‌گیرد. این معادل آن است که بتوانیم آیتم $i$ را چندین بار در کوله‌پشتی قرار دهیم، که با مسئله کوله‌پشتی کامل سازگار است و نه با مسئله کوله‌پشتی ۰-۱.

کوله‌پشتی چندگانه

کوله‌پشتی چندگانه نیز نوعی از کوله‌پشتی ۰-۱ است. تفاوت اصلی این است که از هر آیتم، به جای ۱ عدد، $k_i$ عدد وجود دارد.

توضیح

یک ایده بسیار ساده این است: «انتخاب هر آیتم به تعداد $k_i$ بار» معادل است با «$k_i$ عدد از همان آیتم به صورت تک به تک انتخاب شوند». بدین ترتیب مسئله به مدل کوله‌پشتی ۰-۱ تبدیل می‌شود، که می‌توان آن را با تابع انتقال زیر توصیف کرد:

$$f_{i, j} = \max_{k=0}^{k_i}(f_{i-1,j-k\cdot w_i} + k\cdot v_i)$$

پیچیدگی زمانی این فرآیند $O(W\sum\limits_{i=1}^{n}k_i)$ است.

بهینه‌سازی با گروه‌بندی دودویی

برای بهینه‌سازی، همچنان تبدیل مدل کوله‌پشتی چندگانه به مدل کوله‌پشتی ۰-۱ را در نظر می‌گیریم. پیچیدگی زمانی $O(Wn)$ را نمی‌توان با رویکرد بالا بیشتر بهینه کرد، بنابراین بر روی جزء $O(\sum k_i)$ تمرکز می‌کنیم.

فرض کنید $A_{i, j}$ نشان‌دهنده $j$-امین آیتم جدا شده از آیتم $i$-ام باشد. در رویکرد ساده‌ای که در بالا بحث شد، $A_{i, j}$ برای تمام $j \leq k_i$ نشان‌دهنده یک آیتم یکسان است. دلیل اصلی کارایی پایین ما این است که کارهای تکراری زیادی انجام می‌دهیم. برای مثال، انتخاب $\{A_{i, 1},A_{i, 2}\}$ و انتخاب $\{A_{i, 2}, A_{i, 3}\}$ را در نظر بگیرید. این دو وضعیت کاملاً معادل هستند. بنابراین، بهینه‌سازی روش تقسیم‌بندی، پیچیدگی زمانی را به شدت کاهش خواهد داد.

با استفاده از گروه‌بندی دودویی، این فرآیند کارآمدتر می‌شود.

به طور خاص، $A_{i, j}$ شامل $2^j$ آیتم مجزا است ($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$). اگر $k_i + 1$ یک توان صحیح از ۲ نباشد، یک بسته دیگر به اندازه $k_i-(2^{\lfloor \log_2(k_i+1)\rfloor}-1)$ برای جبران باقیمانده استفاده می‌شود.

از طریق روش تقسیم‌بندی بالا، می‌توان با انتخاب چند $A_{i, j}$، به هر ترکیبی با تعداد $\leq k_i$ آیتم دست یافت. پس از تقسیم هر آیتم به روش توصیف شده، کافی است از روش کوله‌پشتی ۰-۱ برای حل فرمول‌بندی جدید مسئله استفاده کنیم.

این بهینه‌سازی پیچیدگی زمانی $O(W\sum\limits_{i=1}^{n}\log k_i)$ را به ما می‌دهد.

پیاده‌سازی

index = 0;
for (int i = 1; i <= n; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

بهینه‌سازی با Monotone Queue

در این بهینه‌سازی، هدف ما تبدیل مسئله کوله‌پشتی به یک مسئله maximum queue است.

برای سهولت در توصیف، فرض کنید $g_{x, y} = f_{i, x \cdot w_i + y}$ و $g'_{x, y} = f_{i-1, x \cdot w_i + y}$ باشد. در این صورت، رابطه انتقال را می‌توان به صورت زیر نوشت:

$$g_{x, y} = \max_{k=0}^{k_i}(g'_{x-k, y} + v_i \cdot k)$$

علاوه بر این، فرض کنید $G_{x, y} = g'_{x, y} - v_i \cdot x$ باشد. در این صورت، رابطه انتقال را می‌توان به صورت زیر بیان کرد:

$$g_{x, y} \gets \max_{k=0}^{k_i}(G_{x-k, y}) + v_i \cdot x$$

این رابطه به فرم کلاسیک بهینه‌سازی با monotone queue تبدیل می‌شود. مقدار $G_{x, y}$ را می‌توان در زمان $O(1)$ محاسبه کرد، بنابراین برای یک $y$ ثابت، می‌توانیم $g_{x, y}$ را در زمان $O(\lfloor \frac{W}{w_i} \rfloor)$ محاسبه کنیم. در نتیجه، پیچیدگی یافتن تمام مقادیر $g_{x, y}$ برابر $O(\lfloor \frac{W}{w_i} \rfloor) \times O(w_i) = O(W)$ است. به این ترتیب، پیچیدگی کل الگوریتم به $O(nW)$ کاهش می‌یابد.

کوله‌پشتی ترکیبی

مسئله کوله‌پشتی ترکیبی شامل ترکیبی از سه مسئله توصیف‌شده در بالا است. یعنی، برخی آیتم‌ها فقط یک بار قابل برداشتن هستند، برخی به تعداد نامحدود و برخی دیگر حداکثر $k$ بار.

این مسئله ممکن است در نگاه اول ترسناک به نظر برسد، اما تا زمانی که ایده‌های اصلی مسائل کوله‌پشتی قبلی را درک کرده و آن‌ها را با هم ترکیب کنید، می‌توانید آن را حل کنید. شبه‌کد راه‌حل به صورت زیر است:

for (هر آیتم) {
  if (از نوع کوله‌پشتی ۰-۱ است)
    کد کوله‌پشتی ۰-۱ را اعمال کن;
  else if (از نوع کوله‌پشتی کامل است)
    کد کوله‌پشتی کامل را اعمال کن;
  else if (از نوع کوله‌پشتی چندگانه است)
    کد کوله‌پشتی چندگانه را اعمال کن;
}

مسائل تمرینی