ন্যাপস্যাক হল একটি ব্যাগ। ন্যাপস্যাক সমস্যাটি আইটেমের মান অনুযায়ী ব্যাগে আইটেম রাখতে নিয়ে কাজ করে যাতে মোট মান সর্বাধিক হয়। ০-১ ন্যাপস্যাকে আপনি হয় আইটেমটি পুরোপুরি রাখবেন অথবা ফেলবেন, আংশিক রাখা যায় না।
নমুনা সমস্যা
আইটেমের মান = {20, 25, 40} আইটেমের ওজন = {25, 20, 30} ব্যাগের ক্ষমতা = 50ওজন বিতরণ
25,20 {1,2} 20,30 {2,3} {1,3} ব্যবহার করলে ওজন লিমিট přek্রম করবে। {1,2}: ওজন=45, মান=45 {2,3}: ওজন=50, মান=65সর্বোচ্চ মান ৬৫, তাই আইটেম ২ এবং ৩ ন্যাপস্যাকে রাখব।
০-১ ন্যাপস্যাক প্রোগ্রাম
#include<stdio.h> int max(int a, int b) { if(a>b){ return a; } else { return b; } } int knapsack(int W, int wt[], int val[], int n) { int i, w; int knap[n+1][W+1]; for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) knap[i][w] = 0; else if (wt[i-1] <= w) knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]); else knap[i][w] = knap[i-1][w]; } } return knap[n][W]; } int main() { int val[] = {20, 25, 40}; int wt[] = {25, 20, 30}; int W = 50; int n = sizeof(val)/sizeof(val[0]); printf("The solution is: %d", knapsack(W, wt, val, n)); return 0; }আউটপুট
The solution is: 65
