java - 存储最优解

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

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

例如，通过这些输入，我将得到最佳解决方案:

使用索引 0 的商品(重量 = 20，成本 = 5)和 索引 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 == 解决方案[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]]
}