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 Shared Function KnapSack(capacity As Integer, weight As Integer(), value As Integer(), itemsCount As Integer) As Integer
	Dim K As Integer(,) = New Integer(itemsCount, capacity) {}

	For i As Integer = 0 To itemsCount
		For w As Integer = 0 To capacity
			If i = 0 OrElse w = 0 Then
				K(i, w) = 0
			ElseIf weight(i - 1) <= w Then
				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)
			End If
		Next
	Next

	Return K(itemsCount, capacity)
End Function

Example

									Dim value As Integer() = {60, 100, 120}
Dim weight As Integer() = {10, 20, 30}
Dim capacity As Integer = 50
Dim itemsCount As Integer = 3

Dim result As Integer = KnapSack(capacity, weight, value, itemsCount)

Knapsack Problem

Example

Output