এটি একটি C++ প্রোগ্রাম যা ডাইনামিক প্রোগ্রামিং ব্যবহার করে 0-1 ন্যাপস্যাক সমস্যা সমাধান করে। 0-1 ন্যাপস্যাক সমস্যায়, প্রতিটি আইটেমের ওজন এবং মান দেওয়া থাকে। আমাদের নির্ধারণ করতে হবে প্রতিটি আইটেমের কতটুকু নিবেন যাতে মোট ওজন দেওয়া লিমিটের চেয়ে কম বা সমান থাকে এবং মোট মান সর্বাধিক হয়।
অ্যালগরিদম
শুরু
প্রতিটি আইটেমের ওজন এবং মান সহ আইটেম সেট ইনপুট নিন
ন্যাপস্যাকের ক্ষমতা সেট করুন
দুটি ইন্টিজারের মধ্যে সর্বাধিক ফেরত দেওয়া একটি ফাংশন তৈরি করুন।
যে ফাংশনটি W ক্ষমতার একটি ন্যাপস্যাকে রাখা সম্ভাব্য সর্বাধিক মান ফেরত দেয় তা তৈরি করুন
int knapSack(int W, int w[], int v[], int n)
int i, wt;
int K[n + 1][W + 1]
i = 0 থেকে n পর্যন্ত
wt = 0 থেকে W পর্যন্ত
if (i == 0 or wt == 0)
K[i][wt] = 0
else if (w[i - 1] <= wt)
Compute: K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt])
else
K[i][wt] = K[i - 1][wt]
K[n][W] ফেরত দিন
ফাংশনটি কল করুন এবং প্রিন্ট করুন।
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int max(int x, int y) {
return (x > y) ? x : y;
}
int knapSack(int W, int w[], int v[], int n) {
int i, wt;
int K[n + 1][W + 1];
for (i = 0; i <= n; i++) {
for (wt = 0; wt <= W; wt++) {
if (i == 0 || wt == 0)
K[i][wt] = 0;
else if (w[i - 1] <= wt)
K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);
else
K[i][wt] = K[i - 1][wt];
}
}
return K[n][W];
}
int main() {
cout << "ন্যাপস্যাকে আইটেমের সংখ্যা লিখুন:";
int n, W;
cin >> n;
int v[n], w[n];
for (int i = 0; i < n; i++) {
cout << "আইটেম " << i << " এর মান ও ওজন লিখুন:";
cin >> v[i];
cin >> w[i];
}
cout << "ন্যাপস্যাকের ক্ষমতা লিখুন";
cin >> W;
cout << knapSack(W, w, v, n);
return 0;
}
আউটপুট
ন্যাপস্যাকে আইটেমের সংখ্যা: 4 আইটেম 0 এর মান ও ওজন: 10 50 আইটেম 1 এর মান ও ওজন: 20 60 আইটেম 2 এর মান ও ওজন: 30 70 আইটেম 3 এর মান ও ওজন: 40 90 ন্যাপস্যাকের ক্ষমতা: 100 40
