Created
September 19, 2016 21:19
-
-
Save MattPatrickMeyer/f696f79735df84f280cdeb71389c1cbc to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| using System.Linq; | |
| using System.Text; | |
| namespace ConsoleApplication2 | |
| { | |
| class KnapSack | |
| { | |
| // Returns the max value that can be put in a knapscak of capacity W | |
| static int knapSack(int W, int[] wt, int[] val, int n) | |
| { | |
| // Base case | |
| if (n == 0 || W == 0) | |
| { | |
| return 0; | |
| } | |
| // If weight of the nth item is more than Knapsack capacity W, then this item cannot be included in the optimal solution | |
| if (wt[n - 1] > W) | |
| { | |
| return knapSack(W, wt, val, n - 1); | |
| } | |
| // Return the maximum of two cases: | |
| // 1 - nth item included | |
| // 2 - nth item not included | |
| return Math.Max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), | |
| knapSack(W, wt, val, n - 1)); | |
| } | |
| static void Main(string[] args) | |
| { | |
| int[] values = new int[] { 60, 100, 120 }; | |
| int[] weights = new int[] { 10, 20, 30 }; | |
| int W = 50; // Max weight | |
| int n = values.Count(); | |
| Console.WriteLine(knapSack(W, weights, values, n)); | |
| Console.ReadKey(); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment