A practical solution to Knapsack problem with the list of items selected (using Dynamic Programming)
namespace ConsoleKnapsack
{
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
{
static void Main(string[] args)
{
var knapsack = new Knapsack();
double ask = 10;
Stopwatch watch = new Stopwatch();
watch.Start();
var value = knapsack.GetMaxValueForSize(ask);
watch.Stop();
double totalSize = 0;
foreach (var take in value.Item2.Keys.ToList())
{
if (value.Item2[take])
{
Console.Write(take + "|" + knapsack.items[take].Item1 + "|" + knapsack.items[take].Item2 + " ");
totalSize += knapsack.items[take].Item1;
}
}
Console.WriteLine("");
Console.WriteLine("Total Size = " + totalSize);
Console.WriteLine("Asked for Size = " + ask);
Console.WriteLine("Max Calculated Value = " + value.Item1 + "\n");
Console.WriteLine("Dictionary Hit Count = " + knapsack.HitCount);
Console.WriteLine("Elapsed = " + watch.ElapsedMilliseconds);
Console.ReadLine();
}
}
class Knapsack
{
public List<Tuple<double, double>> items = new List<Tuple<double, double>>
{
new Tuple<double, double>(1.1, 1.2),
new Tuple<double, double>(1.3, 1.4),
new Tuple<double, double>(0.5, 0.8),
new Tuple<double, double>(1.1, 2.1),
new Tuple<double, double>(0.5, 0.5),
new Tuple<double, double>(1.0, 1.2),
new Tuple<double, double>(1.4, 1.6),
new Tuple<double, double>(0.6, 0.8),
new Tuple<double, double>(1.2, 1.1),
new Tuple<double, double>(0.9, 1.5),
};
public long HitCount = 0;
public Knapsack()
{
this.items = new List<Tuple<double, double>>();
var rand = new Random();
for (long i = 0; i < 50; i++)
{
double weight = 0.01 + rand.Next(0, 100) / 100.0;
double size = rand.Next(0, 100) / 100.0;
items.Add(new Tuple<double, double>(weight, size));
}
}
Dictionary<double, Dictionary<double, Tuple<double, Dictionary<int, bool>>>> solutions = new Dictionary<double, Dictionary<double, Tuple<double, Dictionary<int, bool>>>>();
// Tuple - size, value
public Tuple<double, Dictionary<int, bool>> GetMaxValueForSize(double size)
{
return this.GetValue(0, size, new Dictionary<int, bool>());
}
private Tuple<double, Dictionary<int, bool>> GetValue(int startItem, double size, Dictionary<int, bool> takes)
{
if (startItem >= items.Count)
{
return new Tuple<double, Dictionary<int, bool>>(0, takes);
}
//var dictionaryKey = startItem.ToString() + "|" + size.ToString();
if (this.solutions.ContainsKey(startItem))
{
var dict = this.solutions[startItem];
if (dict.ContainsKey(size))
{
this.HitCount++;
return dict[size];
}
}
// if we take the item
var item = items.ElementAt(startItem);
var weight = item.Item1;
var value = item.Item2;
Tuple<double, Dictionary<int, bool>> firstTaken;
double firstValue;
if (weight < size)
{
var newTakes = new Dictionary<int, bool>(takes);
newTakes[startItem] = true;
firstTaken = this.GetValue(startItem + 1, size - weight, newTakes);
// firstTaken = this.GetValue(startItem + 1, size - weight, takes);
firstValue = firstTaken.Item1 + value;
}
else
{
firstTaken = new Tuple<double, Dictionary<int, bool>>(0, takes);
firstValue = 0;
}
// if we skip the item
var firstSkipped = this.GetValue(startItem + 1, size, takes);
Tuple<double, Dictionary<int, bool>> returnValue;
if (firstValue >= firstSkipped.Item1)
{
returnValue = new Tuple<double, Dictionary<int, bool>>(firstValue, firstTaken.Item2);
}
else
{
returnValue = firstSkipped;
}
if (this.solutions.ContainsKey(startItem))
{
this.solutions[startItem].Add(size, returnValue);
}
else
{
var dict = new Dictionary<double, Tuple<double, Dictionary<int, bool>>>();
dict.Add(size, returnValue);
this.solutions.Add(startItem, dict);
}
//this.solutions.Add(dictionaryKey, returnValue);
return returnValue;
}
}
}
