০-১ ন্যাপস্যাক প্রব্লেমে, একটি আইটেম সেট দেওয়া থাকে, প্রতিটির একটি ওয়েট এবং একটি ভ্যালু থাকে। আমাদের নির্ধারণ করতে হয় প্রতিটি আইটেমের কতগুলো একটি কালেকশনে থাকবে যাতে টোটাল ওয়েট দিয়ে गये লিমিটের চেয়ে কম বা সমান হয় এবং টোটাল ভ্যালু যতটা সম্ভব বড় হয়।
ইনপুট
Value = [10, 20, 30, 40, 60, 70] Weight=[1, 2, 3, 6, 7, 4] int w=7
আউটপুট
knapsack value is: 100
অ্যালগরিদম
শুরু ইনপুট: প্রতিটির ওয়েট এবং ভ্যালু সহ আইটেম সেট ন্যাপস্যাক ক্যাপাসিটি সেট করুন আইটেমের সংখ্যা = sizeof(values) / sizeof(values[0]) Knapsack(Values (array v-তে স্টোরড), Weights (array w-তে স্টোরড), ম العل নম্বর আইটেম (n), ন্যাপস্যাক ক্যাপাসিটি W) If (w < 0) Return If কোনো আইটেম নেই বা ক্যাপাসিটি ০ হয় Return 0 কারেন্ট আইটেম n ন্যাপস্যাকে ইনক্লুড করুন (v[n]) এবং বাকি আইটেমের জন্য রিকার্স করুন (n - 1) কম হয়ে যাওয়া ক্যাপাসিটি (W - w[n]) দিয়ে কারেন্ট আইটেম n ন্যাপস্যাক থেকে এক্সক্লুড করুন এবং বাকি আইটেমের জন্য রিকার্স করুন (n - 1) ইনক্লুড বা এক্সক্লুড করলে যেটা ম্যাক্সিমাম ভ্যালু দেয় সেটি রিটার্ন করুন শেষ
উদাহরণ কোড
#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
if (W < 0)
return INT_MIN;
if (n < 0 || W == 0)
return 0;
int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
int ex = knapSack(v, w, n - 1, W);
return max (in, ex);
}
int main() {
int v[] = { 10, 20, 30, 40, 60, 70 };
int w[] = { 1, 2, 3, 6, 7, 4 };
int W = 7;
int n = sizeof(v) / sizeof(v[0]);
cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
return 0;
}
আউটপুট
Knapsack value is 100
