Created
September 20, 2016 03:12
-
-
Save MattPatrickMeyer/e2808c121cb38ee73a833babf11187eb 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
| // Init class | |
| class Init | |
| { | |
| static void Main(string[] args) | |
| { | |
| int[] values = new int[] { 60, 100, 120 }; | |
| int[] weights = new int[] { 10, 20, 30 }; | |
| int W = 30; // Max weight | |
| int n = values.Count(); | |
| Console.WriteLine(DynamicKnapSack.knapSack(W, weights, values, n)); | |
| Console.ReadKey(); | |
| } | |
| } | |
| // Naive KnapSack | |
| public class KnapSack | |
| { | |
| // Returns the max value that can be put in a knapscak of capacity W | |
| public 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)); | |
| } | |
| } | |
| // Dynamic Programming KnapSack | |
| public class DynamicKnapSack | |
| { | |
| // Returns the max value that can be put in a knapscak of capacity W | |
| public static int knapSack(int W, int[] wt, int[] val, int n) | |
| { | |
| int[,] K = new int[n+1,W+1]; | |
| // Build table K[,] from the bottom up | |
| for (int i = 0; i <= n; i++) | |
| { | |
| for (int j = 0; j <= W; j++) | |
| { | |
| if (i == 0 || j == 0) | |
| { | |
| K[i,j] = 0; | |
| } | |
| else if (wt[i - 1] <= j) | |
| { | |
| K[i, j] = Math.Max(val[i - 1] + K[i - 1, j - wt[i - 1]], K[i - 1, j]); | |
| } | |
| else | |
| { | |
| K[i, j] = K[i - 1, j]; | |
| } | |
| } | |
| } | |
| return K[n, W]; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment