jain12

0-1 knapsack problem by recursion

Jun 1st, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.42 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int KnapSack(int tot_wt,int wt[],int val[],int n){
  5.   if(tot_wt==0 ||n==0)
  6.     return 0;
  7.     int x=(tot_wt-wt[n-1]>=0)?val[n-1]+KnapSack(tot_wt-wt[n-1],wt,val,n-1):0;
  8.   return max(x,KnapSack(tot_wt,wt,val,n-1));
  9.   }
  10.  
  11. int main(){
  12.   int val[] = { 60, 100, 120 };
  13.   int wt[] = { 10, 20, 30 };
  14.   int W = 50;
  15.   int n = 3;
  16.   cout << KnapSack(W, wt, val, n);
  17.   return 0;
  18.   }
Add Comment
Please, Sign In to add comment