this fuction returns the maximum value that can be put in a knapsack of capacity W
| 4 | |
| 5 | // this fuction returns the maximum value that can be put in a knapsack of capacity W |
| 6 | int knapSack(int W, vector<int> &wt, vector<int> &val , int n) |
| 7 | { |
| 8 | |
| 9 | // Base Case |
| 10 | if (n == 0 || W == 0) |
| 11 | return 0; |
| 12 | |
| 13 | // If weight of the nth item is more |
| 14 | // than Knapsack capacity W, then |
| 15 | // this item cannot be included |
| 16 | // in the optimal solution |
| 17 | if (wt[n - 1] > W) |
| 18 | return knapSack(W, wt, val, n - 1); |
| 19 | |
| 20 | // Return the maximum of two cases: |
| 21 | // (1) nth item included |
| 22 | // (2) not included |
| 23 | else |
| 24 | return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),knapSack(W, wt, val, n - 1)); |
| 25 | } |
| 26 | |
| 27 | // Driver code |
| 28 | int main() |