ন্যাপস্যাক প্রবলেম#
পূর্বশর্ত জ্ঞান: ডায়নামিক প্রোগ্রামিং পরিচিতি
ভূমিকা#
নিচের উদাহরণটি বিবেচনা করুন:
[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]);আবারও, এক্সিকিউশনের ক্রম লক্ষ্য করুন। নিম্নলিখিত ইনভ্যারিয়েন্ট নিশ্চিত করতে এটি কঠোরভাবে অনুসরণ করতে হবে: $(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;
}