knapsack

knapsack.cs

void Main()
{
	var cart = new List<Item>(){
		
		new Item(){id = 7, cost = .99m, quantity = 1},
		new Item(){id = 8, cost = 4m, quantity = 1},
		new Item(){id = 9, cost = 4.9m, quantity = 1},
	};
	
	var solution = CalculateSolution(cart, 5.0m);

	Console.WriteLine("Solution: " + solution.Sum (s => s.cost * s.quantity));
	solution.Dump();
}

List<Item> CalculateSolution(List<Item> cart, decimal maxCost){
	var sortedCart = cart.OrderBy (c => c.cost).ToList();
	//assume all the decimals have 2 fixed decimals being money
	int intMax = (int)(maxCost * 100);
	var ret = new KnapsackPossibility[cart.Count + 1, intMax + 1];
	
	//init 0 rows and columns
	for(var i = 0; i < cart.Count + 1; i++){
		ret[i, 0] = new KnapsackPossibility(){ benefit = 0, ids = new List<int>() };
	}
	for(var i = 0; i < intMax + 1; i++){
		ret[0, i] = new KnapsackPossibility(){ benefit = 0, ids = new List<int>() };
	}
	
	for(int itemIndex = 1; itemIndex < cart.Count + 1; itemIndex++){
		for(int costIndex = 1; costIndex < intMax + 1; costIndex++){
			var item = sortedCart[itemIndex - 1];
			int costRemainder = costIndex - (int)(item.cost * item.quantity * 100);
			if(costRemainder >= 0){
				var totalBenefit = item.benefit + ret[itemIndex - 1, costRemainder].benefit;
				if(totalBenefit > ret[itemIndex - 1, costIndex].benefit){
					ret[itemIndex, costIndex] = new KnapsackPossibility(){benefit = totalBenefit, ids = ret[itemIndex - 1, costRemainder].ids.Concat(new List<int>(){item.id}).ToList() };
				}else{
					ret[itemIndex, costIndex] = ret[itemIndex - 1, costIndex];
				}
			}else{
				ret[itemIndex, costIndex] = ret[itemIndex - 1, costIndex];
			}
		}
	
	}
	var solution = ret[cart.Count, intMax];
	return cart.Where (c => solution.ids.Contains(c.id)).ToList();
}

public class KnapsackPossibility{
	public decimal benefit {get; set;}
	public List<int> ids {get;set;}
};

// Define other methods and classes here
public class Item{
	public int id{get;set;}
	public decimal cost{get; set;}
	public decimal benefit{get{ return cost;}}
	public int quantity{get;set;}
};