n আইটেমের ওজন এবং মান দেওয়া; কাজ হল ন্যাপস্যাকের সর্বোচ্চ মোট মান পেতে W ক্ষমতার একটি ন্যাপস্যাকে নিম্নলিখিত ওজন এবং মানগুলির জন্য 0/1 ন্যাপস্যাক অনুযায়ী আইটেমগুলি প্রিন্ট করা৷
0/1 ন্যাপস্যাক কি?
ন্যাপস্যাক হল একটি ব্যাগের মতো যা শুধুমাত্র একটি নির্দিষ্ট আকারের বা একটি ব্যাগ যা একটি নির্দিষ্ট পরিমাণ ওজন পরিচালনা করতে পারে। একটি ন্যাপস্যাকে অন্তর্ভুক্ত প্রতিটি আইটেমের কিছু মূল্য (লাভ) এবং কিছু ওজন রয়েছে। আমাদের সেই ওজনগুলি যোগ করতে হবে যা একটি ন্যাপস্যাক ধরে রাখতে পারে এমন মোট ওজন অনুসারে আমাদের সর্বাধিক মুনাফা পাবে৷
সুতরাং আমাদের ওজন আছে, তাদের মান (লাভ) এবং ব্যাগের মোট ওজন যা একটি ন্যাপস্যাক ধরে রাখতে পারে, তাই 0/1 ন্যাপস্যাকে আমরা কেবল 1 এবং 0 উল্লেখ করি যে আইটেমটি অন্তর্ভুক্ত বা না যেখানে 0 আইটেমটির জন্য t একটি ব্যাগে যোগ করা হবে, যেখানে 1 হল সেই আইটেমের জন্য যা ন্যাপস্যাকে অন্তর্ভুক্ত করা যেতে পারে।
একটি সাধারণ উদাহরণের সাহায্যে বোঝা যাক -
Let us assume val[] = {1, 2, 5, 6}//value or profit
wt[] = {2, 3, 4, 5}//weight
W = 8//Capacity এর ন্যাপস্যাক টেবিল হবে −
knapsack.jpg
ন্যাপস্যাক টেবিলটি নিম্নলিখিত সূত্রের সাহায্যে পূরণ করা যেতে পারে -
K [i ,w] =সর্বোচ্চ {K [i−1, w], K [i−1, w−wt [i]] + Val[i]}
ব্যাকট্র্যাকিং পদ্ধতি ব্যবহার করে টেবিল সমাধান করা,
এখন আমাদের কাছে প্রতিটি আইটেমের লাভের ডেটা রয়েছে এবং নির্দিষ্ট আইটেমগুলি যোগ করার পরে আমরা সর্বোচ্চ ওজনের মধ্যে সর্বাধিক লাভ পেতে পারি।
- ব্যাকট্র্যাকিং ফর্ম k[n][w] শুরু করুন, যেখানে k[n][w] হল 8।
- আমরা উপরের দিকে যাব কারণ নীল তীরটি কালো তীরগুলি যেদিকে যাচ্ছে সেদিকে সমস্ত পথ নির্দেশ করে৷ সুতরাং 8টি শুধুমাত্র 4র্থ সারিতে আছে তাই আমরা 4র্থ বস্তুটি অন্তর্ভুক্ত করব, এর মানে আমরা 4র্থ আইটেমটি যোগ করার পর সর্বাধিক লাভ পেয়েছি।
- আমরা ৪র্থ আইটেম যোগ করে প্রাপ্ত লাভের সাথে 8 হবে মোট মুনাফাকে বিয়োগ করব, অর্থাৎ 6 আমরা 2 পাব।
- সর্বোচ্চ মুনাফা হিসাবে আমরা 2 কখন পাব তা দেখার জন্য আমরা টেবিলটি ব্যাকট্র্যাক করব। আমরা এটি পেয়েছি যখন আমরা ২য় আইটেম যোগ করি
- সুতরাং আমরা ব্যাগটি দক্ষতার সাথে পূরণ করতে এবং সর্বোচ্চ মুনাফা অর্জনের জন্য একটি ন্যাপস্যাকে ২য় এবং ৪র্থ আইটেম যোগ করব।
উদাহরণ
Input: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
Output: 220 //max value
30 20 //weights
Explanation: to reach till the maximum weight i.e. 50 we will add two weights value,
30 whose value is 120 and 20 whose value is 100
Input: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
Output: 50
4 2
Explanation: to reach till the maximum weight i.e. 6 we will add two weights value, 4
whose value is 40 and 2 whose value is 10. অ্যালগরিদম
Start
Step 1-> In function max(int a, int b)
Return (a > b) ? a : b
Step 2-> In function printknapSack(int W, int wt[], int val[], int n)
Decalare i, w, K[n + 1][W + 1]
Loop For i = 0 and i <= n and i++
Loop For w = 0 and w <= W and w++
If i == 0 || w == 0 then,
Set K[i][w] = 0
Else If wt[i - 1] <= w then,
Set K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
Else
Set K[i][w] = K[i - 1][w]
Set res = K[n][W]
Print res
Set w = W
Loop For i = n and i > 0 && res > 0 and i--
If res == K[i - 1][w] then,
Continue
Else {
Print wt[i - 1])
Set res = res - val[i - 1]
Set w = w - wt[i - 1]
Step 3-> In function int main()
Set val[] = { 50, 120, 70 }
Set wt[] = { 10, 20, 30 }
Set W = 50
Set n = sizeof(val) / sizeof(val[0])
Call function printknapSack(W, wt, val, n)
Stop উদাহরণ
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
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];
}
}
// stores the result of Knapsack
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];
}
}
}
// main code
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
