Dynamic Programming Knapsack Solver Algorithm
The Dynamic Programming Knapsack Solver Algorithm is a powerful technique used to solve the classic knapsack problem, which arises in various computer science, mathematics, and optimization contexts. The problem can be stated as follows: given a set of items, each with a specific weight and value, determine the optimal combination of items to include in a knapsack such that the total value is maximized, while not exceeding a given weight capacity. The Dynamic Programming (DP) approach to solving this problem involves breaking it down into a series of overlapping subproblems, and building a solution by combining the results of these subproblems in an efficient and systematic manner.
The DP Knapsack Solver Algorithm uses a bottom-up approach by constructing a table to store solutions to subproblems. The table has rows representing the items and columns representing the available weight capacities. Each cell in the table contains the maximum value that can be obtained by considering a subset of items and a specific weight capacity. The algorithm iterates through the table, filling in each cell by either including or excluding the current item, depending on whether it leads to a higher total value without exceeding the weight capacity. This process continues until the entire table is filled, and the optimal solution can be found in the cell corresponding to the last item and the maximum weight capacity. By caching and reusing the solutions to overlapping subproblems, the DP Knapsack Solver Algorithm significantly reduces the time complexity compared to a naive recursive approach, resulting in an efficient and practical solution for the knapsack problem.
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;
}
}
}
