存储最优解

Question

我有这个代码：

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);
    }

此代码将 weights 数组和 costs 数组作为输入，并计算给定的最小可能成本最低体重。我实际上还需要知道该解决方案使用了哪些项目。

例如，对于这些输入，我会将其作为我的最佳解决方案：

使用位于 index 0 的项目（重量 = 20，成本 = 5）和位于 [=26 的项目=]index 3(权重=30,成本=6).

这将给我最低成本，对于大于或等于重量的 11，在这种情况下为 50。

代码有效并给出了答案 11，这是最低成本，但它没有给出导致此解决方案的实际项目。您能否帮助稍微更改一下代码，以便它也可以确定哪些项目导致最佳解决方案？

Answer 1

当您执行以下操作时：

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

你不知道现有的解决方案还是新的解决方案是最好的，所以你应该这样做：

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

现在要存储最佳解决方案，您只需要知道上次最佳选择是什么，然后向后迭代/递归重构解决方案。

例如，在上面的代码中，您知道您的最佳解决方案包括第 i 项。因此，您只需使用以下代码更新您的最佳解决方案：

   solutions[j] = i;

然后当你完成后，你总是可以重建你的解决方案，知道它是建立在 solutions[j - weights[solutions[j]]] 上的，重复这个回溯直到 -1 == solutions[j]。

将所有这些放在一起，我们得到：

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]]
}

存储最优解

Store the optimal solution

java

algorithm

optimization

knapsack-problem

dynamic-programming