Knapsack Problem

The knapsack problem (a.k.a rucksack problem) is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

									public static int KnapSack(int capacity, int[] weight, int[] value, 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(value[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];
}

Example

									int[] value = { 60, 100, 120 };
int[] weight = { 10, 20, 30 };
int capacity = 50;
int itemsCount = 3;

int result = KnapSack(capacity, weight, value, itemsCount);

Knapsack Problem

Example

Output