Knapsack Problem

Below we will look at a program in Excel VBA that solves a small instance of a knapsack problem.

Definition: Given a set of items each with a weight and a value determine the items to include in a collection so that the total value is as large as possible and the total weight is less than a given limit. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Example: 5 items with weights values and limit as given.

In Excel this problem looks as follows:

1. First we declare five variables of type Double with names limit weight value totalWeight and maximumValue.

Dim limit As Double weight As Double value As Double totalWeight As Double maximumValue As Double

2. Next we declare five variables of type Integer with with names i j k l m.

Dim i As Integer j As Integer k As Integer l As Integer m As Integer

3. We initialize two variables. We initialize the variable limit with the value of cell D6. We initialize the variable maximumValue with value 0.

limit = Range(“D6”).value
maximumValue = 0

4. Next we check each possible solution. We can either include an item (1) or leave it out (0). We start 5 For Next loops. One for each item.

For i = 0 To 1
For j = 0 To 1
For k = 0 To 1
For l = 0 To 1
For m = 0 To 1

5. We calculate the weight and the value of a possible solution.

weight = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
value = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m

6. Only if value is higher than maximumValue and weight is lower than limit we’ve found a new better solution.

If value > maximumValue And weight <= limit Then

7. If true we write the new solution to row 4 weight to totalWeight and value to maximumValue.

Range(“B4”).value = i
Range(“C4”).value = j
Range(“D4”).value = k
Range(“E4”).value = l
Range(“F4”).value = m
totalWeight = weight
maximumValue = value

8. Don’t forget to close the If statement.

End If

9. Don’t forget to close the 5 For Next loops.

Next m
Next l
Next k
Next j
Next i

Excel VBA checks each possible solution this way and as a result the optimal solution will appear in row 4. Remember 1 means we include an item 0 means we leave it out.

10. Finally write totalWeight and maximumValue of the optimal solution to respectively cell B6 and B8.

Range(“B6”).value = totalWeight
Range(“B8”).value = maximumValue

11. Test the program.

Result:

Conclusion: it’s optimal to include the last four items with a maximum value of 15. This solution with a total weight of 2 + 1 + 1 + 4 = 8 does not exceed the limit of 15.

Note: by making the weights and values variable you can solve any knapsack problem of this size (see downloadable Excel file).