ন্যাপস্যাক প্রবলেম#

পূর্বশর্ত জ্ঞান: ডায়নামিক প্রোগ্রামিং পরিচিতি

ভূমিকা#

নিচের উদাহরণটা দেখো:

[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$

এখান থেকে আমরা ডিপি ট্রানজিশন ইকুয়েশন বের করতে পারি:

$$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]);

আবারও, এক্সিকিউশনের ক্রম লক্ষ্য করো। নিচের ইনভ্যারিয়েন্ট (invariant) নিশ্চিত করতে এটা কঠোরভাবে ফলো করতে হবে: $(i, j)$ জোড়া প্রসেস করার ঠিক আগে, $k > j$ এর জন্য $f_k$ হলো $f_{i,k}$, কিন্তু $k < j$ এর জন্য $f_k$ হলো $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$ কে একাধিকবার ব্যাকপ্যাকে রাখতে পারার সমতুল্য, যেটা কমপ্লিট ন্যাপস্যাক প্রবলেমের সাথে সঙ্গতিপূর্ণ, ০-১ ন্যাপস্যাক প্রবলেমের সাথে নয়।

মাল্টিপল ন্যাপস্যাক#

মাল্টিপল ন্যাপস্যাকও ০-১ ন্যাপস্যাকের একটা ভ্যারিয়েন্ট। প্রধান পার্থক্য হলো প্রতিটা আইটেম মাত্র $1$ টার পরিবর্তে $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}$ হলো $i$ তম আইটেম থেকে বিভক্ত $j$ তম আইটেম। উপরে আলোচিত সরল পদ্ধতিতে, $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;
}

মনোটোন কিউ অপটিমাইজেশন#

এই অপটিমাইজেশনে, আমরা ন্যাপস্যাক প্রবলেমকে একটি ম্যাক্সিমাম কিউ প্রবলেমে রূপান্তর করতে চাই।

বর্ণনার সুবিধার জন্য, ধরো $g_{x, y} = f_{i, x \cdot w_i + y} ,\space 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$$

এটি একটি ক্লাসিক মনোটোন কিউ অপটিমাইজেশন ফর্মে রূপান্তরিত হয়। $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 (each item) {
  if (0-1 knapsack)
    Apply 0-1 knapsack code;
  else if (complete knapsack)
    Apply complete knapsack code;
  else if (multiple knapsack)
    Apply multiple knapsack code;
}

অনুশীলন সমস্যা#