The Old Knapsack Algorithm - Would like to see quantities

[Bill Tillman]

The KnapSack class returns only the value of the items in the sack. I'm trying to find a way to have it also return the quantity of the items, for example how many of item 1, item 2, etc... Obviously there will be times it doesn't use all the items but once the capacity has been reached I want to solve how many of each item it selected. I tried using a new int[] called Qty[] but when the results come back it's not what I'm expecting and the number of items in the sack is clearly over the capacity. Any assistance would be appreciated and note this code does not work in it's current form.

using System;
namespace KnapsackAlgo
{
class KnapsackAlgorithm
{
static void Main(string[] args)
{
int[] cost = { 5, 3, 4 };
int[] weight = { 1, 2, 4 };
int[] Qty = { 0, 0, 0 };
int capacity = 5;
int itemsCount = cost.Length;

int result = Knapsack.KnapSack(capacity, weight, cost, itemsCount);
Console.WriteLine("{0,8:C}", result);
Console.WriteLine("Qty of item #1 {0}", Qty[1]);
Console.WriteLine("Qty of item #2 {0}", Qty[2]);
Console.WriteLine("Qty of item #3 {0}", Qty[3]);
}
}
public class Knapsack
{
public static int KnapSack(int capacity, int[] weight, int[] cost, int itemsCount)
{
int[,] K = new int[itemsCount + 1, capacity + 1];

for (int i = 0; i <= itemsCount; ++i)
{
for (int w = 0; w <= capacity; ++w)
{
if (i == 0 || w == 0)
K[i, w] = 0;
else if (weight[i - 1] <= w)
K[i, w] = Math.Max(cost[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);
else
K[i, w] = K[i - 1, w];
}
}
return K[itemsCount, capacity];
}
}
}

Continue reading...