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?
- 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)?