n সংখ্যক আইটেমের ওজন এবং মান দেওয়া আছে; কাজ হল 0/1 ন্যাপস্যাক অনুযায়ী আইটেমগুলো প্রিন্ট করা নিচের ওজন এবং মানের জন্য একটি ন্যাপস্যাক যার ক্ষমতা W, যাতে ন্যাপস্যাকে সর্বোচ্চ মোট মান পাওয়া যায়।
0/1 Knapsack কী?
ন্যাপস্যাক হল একটি ব্যাগ যার আকার নির্দিষ্ট বা যা একটি নির্দিষ্ট ওজন ধারণ করতে পারে। ন্যাপস্যাকে অন্তর্ভুক্ত প্রতিটি আইটেমের কিছু মান (প্রফিট) এবং কিছু ওজন থাকে। আমাদের সেই ওজনগুলো যোগ করতে হবে যাতে ন্যাপস্যাক যে মোট ওজন ধারণ করতে পারে সেটি মেনে সর্বোচ্চ প্রফিট পাওয়া যায়।
সুতরাং আমাদের ওজন, তাদের মান (প্রফিট) এবং ব্যাগের মোট ওজন আছে যা ন্যাপস্যাক ধারণ করতে পারে, 0/1 ন্যাপস্যাকে আমরা শুধু ১ এবং ০ দিয়ে বলে দিই কোন আইটেমগুলো অন্তর্ভুক্ত হবে বা না যেখানে ০ হল সেই আইটেম যা ব্যাগে যোগ করা যাবে না, ১ হল সেই আইটেম যা ন্যাপস্যাকে অন্তর্ভুক্ত করা যাবে।
সরল উদাহরণ দিয়ে বুঝি:
ধরি val[] = {1, 2, 5, 6} // মান বা প্রফিট
wt[] = {2, 3, 4, 5} // ওজন
W = 8 // ক্ষমতা
ন্যাপস্যাক টেবিল হবে:
knapsack.jpg
ন্যাপস্যাক টেবিল নিচের সূত্র দিয়ে বরাদ্দ করা যায়:
K[i, w] = max{K[i-1, w], K[i-1, w-wt[i]] + Val[i]}
ব্যাকট্র্যাকিং পদ্ধতিতে টেবিল সমাধান করলে:
এখন সব আইটেমের তাদের প্রফিট এবং নির্দিষ্ট ওজনে নির্দিষ্ট আইটেম যোগ করে সর্বোচ্চ প্রফিটের ডেটা আছে।
- k[n][w]- থেকে ব্যাকট্র্যাকিং শুরু করুন, যেখানে k[n][w] হল ৮।
- ব্লু আ روانის সাথে উপরে যাব যেখানে ব্ল্যাক আ روانগুলো যাচ্ছে। ৮ ৪র্থ রোয়ে থাকায় ৪র্থ অবজেক্ট অন্তর্ভুক্ত করব, অর্থাৎ ৪র্থ আইটেম যোগ করলে সর্বোচ্চ প্রফিট পাওয়া যাচ্ছে।
- মোট প্রফিট ৮ থেকে ৪র্থ আইটেম যোগ করে প্রাপ্ত প্রফিট ৬ বিয়োগ করলে ২ পাওয়া যাবে।
- টেবিল ব্যাকট্র্যাক করলে ২ ম্যাক্সিমাম প্রফিট হিসেবে পাওয়া যাবে ২য় আইটেম যোগ করলে।
- তাহলে ২য় এবং ৪র্থ আইটেম ন্যাপস্যাকে যোগ করলে ব্যাগটি দক্ষতার সাথে ভরা যাবে এবং সর্বোচ্চ প্রফিট অর্জন করা যাবে।
উদাহরণ
Input: val[] = {60, 100, 120} wt[] = {10, 20, 30} w = 50
Output: 220 //max value
30 20 //weights
Explanation: সর্বোচ্চ ওজন ৫০ পর্যন্ত পৌঁছাতে ৩০ ওজন (মান ১২০) এবং ২০ ওজন (মান ১০০) যোগ করব।
Input: val[] = {10, 40, 50} wt[] = {2, 4, 5} w = 6
Output: 50 4 2
Explanation: সর্বোচ্চ ওজন ৬ পর্যন্ত পৌঁছাতে ৪ ওজন (মান ৪০) এবং ২ ওজন (মান ১০) যোগ করব।
অ্যালগরিদম
Start
Step 1-> max(int a, int b) ফাংশনে: Return (a > b) ? a : b
Step 2-> printknapSack(int W, int wt[], int val[], int n) ফাংশনে:
Declare i, w, K[n+1][W+1]
Loop i=0 to n: Loop w=0 to W:
If i==0 or w==0: K[i][w]=0
Else if wt[i-1] <= w: K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
Else: K[i][w] = K[i-1][w]
Set res = K[n][W], Print res
Set w = W
Loop i=n down to 1 while res>0:
If res == K[i-1][w]: Continue
Else: Print wt[i-1], res = res - val[i-1], w = w - wt[i-1]
Step 3-> main():
Set val[] = {50, 120, 70}, wt[] = {10, 20, 30}, W = 50
n = sizeof(val)/sizeof(val[0])
Call printknapSack(W, wt, val, n)
Stop
উদাহরণ
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0) K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else K[i][w] = K[i - 1][w];
}
}
int res = K[n][W];
printf("maximum value=%d\n", res);
w = W;
printf("weights included\n");
for (i = n; i > 0 && res > 0; i--) {
if (res == K[i - 1][w]) continue;
else {
printf("%d ", wt[i - 1]);
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
int main() {
int val[] = {50, 120, 70};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0;
}
আউটপুট
maximum value=190 weights included 30 20
