February 16th, 2011, 11:53 AM
Knapsack problem using backtracking
I have to write a program that has a given knapsack weight limit and put items in it with the maximum weight, items doesn't have value only weight.
i.e Knapsack weight limit: 17
items weights : 3, 8, 4, 1, 5, 13
I have to put in it items with the higest weight in this case would be 13 + 4, of course all items will be sorted from the highest one to the lowest one, that I already have.
Can anyone help, Ive been looking on Web for that but I only found examples that have items values and weights.
February 16th, 2011, 12:48 PM
Re: Knapsack problem using backtracking
What if you were to say that all your item values are 1, wouldn't the algorithms you found on internet still work?
Is your question related to IO?
Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
Tags for this Thread
Click Here to Expand Forum to Full Width