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