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!
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.