Sort of knapsack problem.
I`m having problem writing a program, i input N items with their weights, for example item1 = 3kg,item2 = 4kg, the sum of all item`s weight is EVEN. First i need to answer the question, is there a possibility to pack those items to two knapsacks in such a way that weight of knapsack 1 == weight of knapsack2. Any ideas. I just need a clue to start. Cheers.
PS. sorry for my english :)
PS. sorry for my english :)
The first problem you need to solve is the mathematics of the question. Forget C++. If you were given a list of weights and a pencil and paper, how would you solve the problem?
Once you have a mathematical solution to the problem, then we can turn to design and implementation.
The first thing that occurs to me is that if the total weight of all items I(1)...I(n) is W, then there is a solution iff there exists a subset of items whose weight totals W/2. (Note that the set of items may contain only one item).
Once you have a mathematical solution to the problem, then we can turn to design and implementation.
The first thing that occurs to me is that if the total weight of all items I(1)...I(n) is W, then there is a solution iff there exists a subset of items whose weight totals W/2. (Note that the set of items may contain only one item).
@jsmith: well, the mathematical and efficient solution might take some time to find, since that would be a proof of P=NP (the problem is obviously in NP, and it is not in P since the the knapsack problem can be reduced to this modified version in polynomial time, thus it is NP complete).
@Hubson: sorry, but you'll have to try all combinations... (some optimization is possible, but that doesn't change the asymptotic runtime).
@Hubson: sorry, but you'll have to try all combinations... (some optimization is possible, but that doesn't change the asymptotic runtime).
@Hudson: You could use a function minimiser, or a language like R/Splus to do this I would've thought.
Yes, I never said there was a known optimal solution. The point was to get the poster into thinking first how to "solve" the problem before worrying about an implementation. I see it as a two-step process; most students try to go from start to finish in one step IMHO.
Topic archived. No new replies allowed.