Store the optimal solution

user_14405992 0
Viewed 83

I have this code:

public static void main(String[] args) {
       final int[] weights = {20,40,10,30}, costs = {5,20,2,6};
       final int minWeight = 50;
       firstSolution(weights,costs,minWeight);
   }

  public static void firstSolution(int[] weights, int[] costs, int minWeight){
        int maxWeight = 0;

        for(final int weight: weights){
            maxWeight += weight;
        }
        int[] minCost = new int[maxWeight + 1];
        for(int i = 1; i <= maxWeight; i++){
            minCost[i] = Integer.MAX_VALUE;
        }
        for(int i = 0; i < weights.length; i++){
            for(int j = maxWeight; j >= weights[i]; j--){
                if(minCost[j - weights[i]] != Integer.MAX_VALUE){
                    minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);
                }
            }
        }
        int answer = Integer.MAX_VALUE;

        for(int i = minWeight; i <= maxWeight; i++){
            answer = Math.min(answer, minCost[i]);
        }
        System.out.println(answer);
    }

This codes takes as input an array of weights and an array of costs, and it calculates the least possible cost for the given minimum Weight. I actually need to also have which item's are used for this solution.

For example with these inputs i would have as my optimal solution :

Use item at index 0 (weight = 20, cost = 5) and item at index 3(weight = 30, cost = 6).

This will give me the minimum cost which is 11 for more than or equal weight which is 50 in this case.

The code works and gives me answer 11 which is the minimum cost, but it doesn't give me the actual items that led to this solutions. Could you help with changing the code a bit so it can also determine which items lead to the optimal solution?

knapsack-problem dynamic-programming optimization algorithm java
1 Answers

When you do the following:

minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);

you don't know if the existing solution or the new solution are the best one, so instead you should do:

if (minCost[j - weights[i]] + costs[i] < minCost[j]) {
    minCost[j] = minCost[j - weights[i]] + costs[i];
    // And update the storage of the best solution here.
}

Now to store a best solution, you only need to know what was your last best choice, and then iterate / recurse backwards to reconstruct the solution.

For instance, in the above code you know your optimal solution includes item i. So you can simply update your best solution with the following code:

   solutions[j] = i;

And then when you're done you can always reconstruct your solution knowing that it was built on solutions[j - weights[solutions[j]]], repeating this backtracking until -1 == solutions[j].

Putting this all together, we get:

while (-1 != solution[W]) {
    // This prints the last item picked and its corresponding weight.
    print solution[W] + ": " + weight[solution[W]]
    // This updates the total weight to refer to the
    // optimal sub-solution that we built upon.
    W = W - weight[solution[W]]
}
user_89813450
Related