Win a copy of Serverless Applications with Node.js this week in the NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • paul wheaton
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Ron McLeod
  • Tim Moores
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Vijitha Kumara

Knapsack with exact weight and minimum total cost of items  RSS feed

 
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, my question is more about programing than java in particular. I want to make a Java program that for given items that have a weight and a cost, fills a knapsack of capacity C with items that have exactly C weight (or as close to C as possible) with the minimum cost possible (each item can be selected only once). I want to use dynamic programing and I am having trouble finding the recursive relation for this problem. I found this article: https://www.researchgate.net/publication/308337819_An_Effective_Dynamic_Programming_Algorithm_for_the_Minimum-Cost_Maximal_Knapsack_Packing but I cant understand the recursive relation and the pseudocode with all this mathematical bs... Can you describe what the recursive relation would be for this problem, or even provide some code? Thanks is advance!
 
Saloon Keeper
Posts: 5759
56
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You need some structure or Collection that represents the "state" of your bag. A part of the state needs to identify all the items in the bag at a given point in time and their sum weight and sum cost. You start out with an initial state for an empty bag.

You enter your recursive method with a state.
You look to see what you can add to the state that will not exceed the weight.
If that state has been tried before, return null.
If it is the exact weight, see of the cost is less than the last state that had the exact weight, then return the state.
If it is less than the weight, take the new state and pass it to the next call to the method.
If it is greater than the weight, return null.

The answer will be returned as you unwind the recursion back to the original call.

There are some subtleties not mentioned here, like, "almost" exact weight, but this is the general gist.
 
Curse your sudden but inevitable betrayal! And this tiny ad too!
global solutions you can do at home or in your backyard
https://www.kickstarter.com/projects/paulwheaton/better-world-boo
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!