ডায়নামিক প্রোগ্রামিং ব্যবহার করে ন্যাপস্যাক সমস্যা সমাধানের জন্য C++ প্রোগ্রাম

এটি একটি C++ প্রোগ্রাম যা ডায়নামিক প্রোগ্রামিং ব্যবহার করে 0-1 ন্যাপস্যাক সমস্যার সমাধান করতে পারে। 0-1 ন্যাপস্যাক সমস্যায়, আইটেমগুলির একটি সেট দেওয়া হয়, প্রতিটির ওজন এবং একটি মান। একটি সংগ্রহে অন্তর্ভুক্ত করার জন্য আমাদের প্রতিটি আইটেমের সংখ্যা নির্ধারণ করতে হবে যাতে মোট ওজন প্রদত্ত সীমার চেয়ে কম বা সমান হয় এবং মোট মান যতটা সম্ভব বড় হয়৷

অ্যালগরিদম

BeginInput আইটেম সেট প্রতিটি একটি ওজন এবং একটি valueSet knapsack ধারণক্ষমতা এমন একটি ফাংশন তৈরি করুন যা সর্বাধিক দুটি পূর্ণসংখ্যা প্রদান করে৷ একটি ফাংশন তৈরি করুন যা সর্বাধিক মান প্রদান করে যা ক্ষমতার একটি ন্যাপস্যাকে রাখা যেতে পারে Wint knapSack(int W, int w) [], int v[], int n)int i, wt;int K[n + 1][W + 1] এর জন্য i =0 থেকে nfor wt =0 থেকে Wif (i ==0 বা wt ==0) K[i][wt] =0 অন্যথায় যদি (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] রিটার্ন K[n][W] ফাংশন কল করুন এবং প্রিন্ট করুন। শেষ

উদাহরণ কোড

#include  namespace ব্যবহার করে std;int max(int ​​x, int y) { রিটার্ন (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++) { (wt =0; wt <=W; wt++) { যদি (i ==0 || wt ==0) K[i][wt] =0; অন্যথায় যদি (w[i - 1] <=wt) K[i][wt] =max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]); অন্যথায় K[i][wt] =K[i - 1][wt]; } } K[n][W];}int main() { cout <<"একটি ন্যাপস্যাকে আইটেমের সংখ্যা লিখুন:"; int n, W; cin>> n; int v[n], w[n]; (int i =0; i > v[i]; cin>> w[i]; } cout <<"ন্যাপস্যাকের ক্ষমতা লিখুন"; cin>> W; cout < 
আউটপুট
 
 একটি ন্যাপস্যাকে আইটেমের সংখ্যা লিখুন:4 আইটেমের মান এবং ওজন লিখুন 0:1050 আইটেমের মান এবং ওজন লিখুন 1:2060 আইটেমের মান এবং ওজন লিখুন 2:3070 আইটেমের জন্য মান এবং ওজন লিখুন 3:4090 ন্যাপস্যাকের ক্ষমতা লিখুন<10040 /প্রে>