Knapsack Problem

The original name came from a problem where a hiker tries to pack the most valuable items without overloading the knapsack. Each item has a certain value/benefit and weight. An overall weight limitation gives the single constraint.

This is a combinatorial optimization problem and has been studied since 1897. Several algorithms have been developed to solve this problem. Application examples:

• Stocking warehouse to the space limit
• Finding the least wasteful way to cut raw materials
• Portfolio selection in investment decision
• Capital budgeting allocation decision
• Project selection

Let’s use the following notations.  The objective function is to maximize the total value of items selected while the constraint is to ensure the total weight is no more than the weight limitation.

We are trying to decide which items to carry within the 15 kg backpack limit so that the total item values are maximized. We setup the spreadsheet as follows:

We need to enable Excel Solver before we can use it. From Excel, select File then Option. Select Add-Ins. The Add-Ins manager will then appear. At the bottom of the screen, hit the “Go” radio button next to Manage Excel Adds-Ins. Check the Solver Add-In box and Solver will be enabled. To access Excel Solver, go to Data and the Solver radio button will appear.

We need to setup the Solver as follows:

After hitting the Solve radio button, the solution we get is as follows. It means we should take items 2, 3, 4 and 5 in the backpack.

The same exact Excel model can be used to decide on project budgeting (which projects to select based on total budget available), investment decision (which portfolio to select based on total investment amount), and many more.

Please send me email if you would like to learn more about this and keen to get the Excel Solver Knapsack model.