Its amazing to see people actually taking the time to read ginormous walls of text and giving feedback, so thank you! afaik Knapsack as originally stated is in

Its amazing to see people actually taking the time to read ginormous walls of text and giving feedback, so thank you! 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-continuous-non-distinct-constraint http://stackoverflow.com/questions/8860882/knapsack-with-con... [2] http://en.wikipedia.org/wiki/Continuous_knapsack_problem http://en.wikipedia.org/wiki/Continuous_knapsack_problem [3] http://en.wikipedia.org/wiki/Criss-cross_algorithm http://en.wikipedia.org/wiki/Criss-cross_algorithm