Books on a shelf exercise
Hi, I got a C++ exercise for school and I got to a point where I can't figure out how to make it work (it's not that I can't solve it in C++, but I haven't figured out an algorithm for solving it).
The assignment is this:
Joe wants to learn more about his computer. He has a shelf of L cm. He has n books available to buy, each with it's width.
You must buy as many books as you can't (can't but the same twice) in order to completely use the space available on the shelf (variable L).
I don't have a lot so far, since the biggest part is the solving algorithm. I sorted the list of books from smallest to biggest, but nothing more. Please help me with some ideas for solving it.
Thanks in advance,
Chris
The assignment is this:
Joe wants to learn more about his computer. He has a shelf of L cm. He has n books available to buy, each with it's width.
You must buy as many books as you can't (can't but the same twice) in order to completely use the space available on the shelf (variable L).
I don't have a lot so far, since the biggest part is the solving algorithm. I sorted the list of books from smallest to biggest, but nothing more. Please help me with some ideas for solving it.
Thanks in advance,
Chris
This, my friend, is a slightly simplified knapsack problem.
http://en.wikipedia.org/wiki/Knapsack_problem
Given that n is a finite value, you might simply try a brute force solution.
http://en.wikipedia.org/wiki/Knapsack_problem
Given that n is a finite value, you might simply try a brute force solution.
Last edited on
Topic archived. No new replies allowed.