Divide prices of items between two people in the most even way possible, so if they get a fridge for 100 bucks, tv for 250, and a couch for 400. ONe person would have to buy the fridge and tv, and the other would buy the couch. What would be the best way to sovlve this problem?
by "thefalling"
It sounds like it has come straight from some course work but it lead me to an interesting wikipedia article: http://en.wikipedia.org/wiki/Knapsack_problem
My response was to sort the costs starting with the highest price with one person, switch to the other person and keep adding until they have paid more, then switch back to the other person and continue.
I'm currently doing some reading to find out if there is a better way to do it and whether my method is actually correct.
My other suggestion was to work out all possible combinations and determine which comes out the closest. Obviously brute force could cause performance to go out the window, but since the suggested size of items to be included was small, it is _a_ solution.
I'm interested in anyone else's thoughts on it. I'll put up a reply to this if I find anything intriguing.
