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.

									static int Max(int val1, int val2) {
	return (val1 > val2) ? val1 : val2;
}

static int** Create2DArray(int rowCount, int colCount) {
	int** arr = new int*[rowCount];

	for (int i = 0; i < rowCount; ++i)
		arr[i] = new int[colCount];

	return arr;
}

static int KnapSack(int capacity, int weight[], int value[], int itemsCount) {
	int** K = Create2DArray(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] = 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