{{ message }}

Instantly share code, notes, and snippets.

# antgustech/Program.cs

Created Sep 20, 2017
Knapsack Fractorial algorithm translated from Geeksforgeeks
 //http://www.geeksforgeeks.org/fractional-knapsack-problem/ class Program { static void Main(string[] args) { new Program(); } public Program() { var items = BuildSortedArrayOfItems(5); var result = FractorialKnapsackAlgorithm(30, items); Console.WriteLine(""); } private double FractorialKnapsackAlgorithm(int maxWeight, Item[] items) { var currentWeight = 0; var resultValue = 0.0; for (int i = 0; i < items.Length; i++) { if (currentWeight + items[i].Weight <= maxWeight) { currentWeight += items[i].Weight; resultValue += items[i].Value; } else { int remains = maxWeight - currentWeight; resultValue += items[i].Value * ((double)remains / items[i].Weight); break; } } return resultValue; } private Item[] BuildSortedArrayOfItems(int size) { var items = new Item[size]; for (var i = 0; i < items.Length; i++) { var value = i * 10 + 5; // just some random value. var weight = i * 6 + 2; // just some random value. var item = new Item { Id = i, Value = value, Weight = weight, ValueDividedWeight = ((double)value / (double)weight) }; items[i] = item; } Array.Sort(items, (x, y) => y.ValueDividedWeight.CompareTo(x.ValueDividedWeight)); return items; } } }
to join this conversation on GitHub. Already have an account? Sign in to comment