afaik Knapsack as originally stated is integer programming ie. it operates over discrete n, and NP-hard, so for large n the compute times are prohibitive. Simplex algorithms operate over continuous n[1], so you have amortized poly or worst-case exponential big O.
In other words, if you were in a fruit market with 1000 different kinds of fruit & you were not allowed to chop a fruit ( generally the case, you can't walk into Safeway, chop up an apple & walk out with one-eighth of an apple or half a grape or quarter blackberry ), then you'd have Knapsack, & there'd be no easy way to solve it for n=1000. But here you can buy 0.47 pounds of ham & 0.26 pounds of cheese & so forth ie. anything above 0.25 pounds is fair game, so the problem lends itself to a solution in reasonable time even for very large n.
There is a variant of Knapsack called Continuous Knapsack[2], which is solvable in polynomial time, in-fact O(n) if you reformulate a bit. But that isn't the simplex algorithm either.
I guess what I'm saying is - knowing Knapsack & dynamic programming won't help you in this case. I actually solved a very similar problem for BofA a few years ago. We used the commercial version of CPLEX to optimally allocate a couple hundred million dollars to a few million home loan portfolios across the US.
I was actually hoping someone would post a solution using criss-cross[3].
[1] http://stackoverflow.com/questions/8860882/knapsack-with-con... [2] http://en.wikipedia.org/wiki/Continuous_knapsack_problem [3] http://en.wikipedia.org/wiki/Criss-cross_algorithm
And Harry is undoubtedly a resource of incredible value on things that the grocery startup hasn't even considered yet; exactly the sort of senior person they're going to need.
Hiring both of them is the right thing.
I'm not sure how Dick got past the phone interview, though.