I'm developing a "Greedy Algorithm" in C++. The purpose is to maximize the number of items added to a "Knapsack".

To determine the optimal solution (for testing my C++ version), I've used Excel's Solver to determine the best solution. Please see attached XLS.

Something doesn't seem to be working out in the Excel though. If my weight constraint = 900 weight units and I want to maximize "value", why does the Excel solution "select" the following?

Excel:

- 9 times item #1. As item number 1 weighs 100 units each, it now meets the weight constraint. However, the maximized total value equals 1350 (9* 150).

- Currently, my C++ version picks the following (I want to proof that both platforms -- Excel & C++ -- provide the same solution):

- (4 times item #3) + (1 times item #1).

- This results in a value of 1950 value units (4*450 + 1*150).... which obviously is the more optimal solution.

So, my question... what's missing in my Excel Solver solution (resulting in 1,350 vs. 1,950 value units)?

Thx,

EEH

Test----Weight-Alone.xls
Is there anything i'm missing? If you are using Office 2007 or more recent, make sure to save your workbook in XLSM format because in XLS it strip every VBA code.