DynamicProgrammingKnapsackSolver.cs

using System;
using System.Collections.Generic;

namespace Algorithms.Knapsack
{
    /// <summary>
    ///     Dynamic Programming Knapsack solver.
    /// </summary>
    /// <typeparam name="T">Type of items in knapsack.</typeparam>
    public class DynamicProgrammingKnapsackSolver<T>
    {
        /// <summary>
        ///     Returns the knapsack containing the items that
        ///     maximize value while not exceeding weight capacity.
        /// </summary>
        /// <param name="items">The list of items from which we select ones to be in the knapsack.</param>
        /// <param name="capacity">
        ///     The maximum weight capacity of the knapsack
        ///     to be filled. Only integer values of this capacity are tried. If
        ///     a greater resolution is needed, multiply the
        ///     weights/capacity by a factor of 10.
        /// </param>
        /// <param name="weightSelector">
        ///     A function that returns the value of the specified item
        ///     from the <paramref name="items">items</paramref> list.
        /// </param>
        /// <param name="valueSelector">
        ///     A function that returns the weight of the specified item
        ///     from the <paramref name="items">items</paramref> list.
        /// </param>
        /// <returns>
        ///     The array of items that provides the maximum value of the
        ///     knapsack without exceeding the specified weight <paramref name="capacity">capacity</paramref>.
        /// </returns>
        public T[] Solve(T[] items, int capacity, Func<T, int> weightSelector, Func<T, double> valueSelector)
        {
            var cache = Tabulate(items, weightSelector, valueSelector, capacity);
            return GetOptimalItems(items, weightSelector, cache, capacity);
        }

        private static T[] GetOptimalItems(T[] items, Func<T, int> weightSelector, double[,] cache, int capacity)
        {
            var currentCapacity = capacity;

            var result = new List<T>();
            for (var i = items.Length - 1; i >= 0; i--)
            {
                if (cache[i + 1, currentCapacity] > cache[i, currentCapacity])
                {
                    var item = items[i];
                    result.Add(item);
                    currentCapacity -= weightSelector(item);
                }
            }

            result.Reverse(); // we added items back to front
            return result.ToArray();
        }

        private static double[,] Tabulate(
            T[] items,
            Func<T, int> weightSelector,
            Func<T, double> valueSelector,
            int maxCapacity)
        {
            // Store the incremental results in a bottom up manner
            var n = items.Length;
            var results = new double[n + 1, maxCapacity + 1];
            for (var i = 0; i <= n; i++)
            {
                for (var w = 0; w <= maxCapacity; w++)
                {
                    if (i == 0 || w == 0)
                    {
                        // If we have no items to take, or
                        // if we have no capacity in our knapsack
                        // we cannot possibly have any value
                        results[i, w] = 0;
                    }
                    else if (weightSelector(items[i - 1]) <= w)
                    {
                        // Decide if it is better to take or not take this item
                        var iut = items[i - 1]; // iut = Item under test
                        var vut = valueSelector(iut); // vut = Value of item under test
                        var wut = weightSelector(iut); // wut = Weight of item under test
                        var valueIfTaken = vut + results[i - 1, w - wut];
                        var valueIfNotTaken = results[i - 1, w];
                        results[i, w] = Math.Max(valueIfTaken, valueIfNotTaken);
                    }
                    else
                    {
                        // There is not enough room to take this item
                        results[i, w] = results[i - 1, w];
                    }
                }
            }

            return results;
        }
    }
}