Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Knapsack Problem - recursive
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace Rextester { public class Program { // Knapsack Problem - recursive public static void Main(string[] args) { int [] values = new int[]{60, 100, 120}; int [] weights = new int[]{10, 20, 30}; int capacity = 50; int n = values.Length; Console.WriteLine(knapSack(capacity, weights, values, n)); } //It returns maximum of two integers static int max(int a, int b) { return (a > b)? a : b; } // Returns the maximum value that can be put in a knapsack of capacity static int knapSack(int capacity, int [] weights, int [] values, int n) { // Base Case - nothing can be included in knapSack as capacity is 0 or no values exists. if (n == 0 || capacity == 0) return 0; // If weight of the nth item is more than Knapsack capacity , then this item cannot be included in the optimal solution if (weights[n-1] > capacity) return knapSack(capacity, weights, values, n-1); // Return the maximum of two cases: // 1. inclusing nth item // 2. without including nth item. else return max( values[n-1] + knapSack(capacity - weights[n-1], weights, values, n-1), knapSack(capacity, weights, values, n-1)); } } }
run
|
edit
|
history
|
help
0
Hash plus i minus
Recursion
número poderoso
Add Two String Numbers which may be large - Author MC
EpsilonComparer
3. Delegates and events, reference pitfall
Brainf*ck interpreter
Classes-and-Structures.cs
Math 9.7 (Added Speed Math)
Games