Author: Not specified Language: java
Description: Not specified Timestamp: 2018-03-14 04:40:54 +0000
View raw paste Reply
  1. int knapSack(int W, int wt[], int val[], int n)
  2. {
  3.    // Base Case
  4.    if (n == 0 || W == 0)
  5.        return 0;
  6.  
  7.    // If weight of the nth item is more than Knapsack capacity W, then
  8.    // this item cannot be included in the optimal solution
  9.    if (wt[n-1] > W)
  10.        return knapSack(W, wt, val, n-1);
  11.  
  12.    // Return the maximum of two cases:
  13.    // (1) nth item included
  14.    // (2) not included
  15.    else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
  16.                     knapSack(W, wt, val, n-1)
  17.                   );
  18. }
View raw paste Reply