Skip to content

Instantly share code, notes, and snippets.

@antgustech
Created September 20, 2017 17:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save antgustech/9749bf51aabd3854999b366e8fc73ff4 to your computer and use it in GitHub Desktop.
Save antgustech/9749bf51aabd3854999b366e8fc73ff4 to your computer and use it in GitHub Desktop.
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