Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment