• Post Reply Bookmark Topic Watch Topic
  • New Topic

knapsack problem - solution set  RSS feed

 
Brandi Love
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have this function, knapsack, which takes in an array of integers, the array size, and the size of the 'knapsack.' The algorithm determines if there is a set of integers that, when added together, will be the same as the size of the knapsack. A simpler way to explain would be I have an array of items of a certain size and I want to know if they can fit exactly into my knapsack. If you're familiar with the exact fit knapsack problem you'll know what I'm talking about.

I've written and tested the function and it appears to be working correctly. My issue is this - I need to figure out a way to make the function also return the set of items that are in a solution. I can't figure out how to and I'm starting to wonder if it is possible with the way I've done this. Can anyone provide me with some sort of guidance to solve this one? Any help is appreciated! The code is below...

 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about passing one of the Collection classes too - perhaps a Stack that gets an Integer added when it is part of the solution?
Bill
 
Brandi Love
Ranch Hand
Posts: 133
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That seems like it could work, I'll give it a shot. Thanks for the advice.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!