查找服务器的最低总停机时间

Question

您有一个数组，它根据服务器的“停机成本”表示一列服务器。您只能访问行两端的服务器(即只能访问第一服务器或最后一台服务器)。

选择服务器的顺序与其停机时间相乘，并添加到“总停机成本”中。

设计一个程序，以找到最小的总停机成本。

例如，对于数组：

[5, 3, 6, 2, 1, 4]

最少的总停机时间是：

5*1 + 4*2 + 3*3 + 6*4 + 2*5 + 1*6 = 62

这是我用来获得这个结果的代码：

public static void main(String[] args){
    int[] serverDowntimes = {5, 3, 6, 2, 1, 4};

    int start = 0;
    int end = serverDowntimes.length - 1;
    long totalCost = 0;
    int serverNumber = 1;
    while(start <= end){
        if(serverDowntimes[start] >= serverDowntimes[end]){
            totalCost += serverNumber * serverDowntimes[start];
            start++; //Increment start (i.e. First server in line was recovered)
        }else{
            totalCost += serverNumber * serverDowntimes[end];
            end--; //Decrement end (i.e. Last server in line was recovered)
        }
        serverNumber++;
    }
    System.out.println(totalCost);
}

但是，当我有以下数组时，我的代码会失败：

[5, 3, 1, 8, 2, 4]

对于这个数组，我的代码输出：

76 (5*1 + 4*2 + 3*3 + 2*4 + 8*5 + 1*6)

然而，更好的答案应该是：

73 (4*1 + 2*2 + 8*3 + 5*4 + 3*5 + 1*6)

如何修改代码，使其也能与类似于以下的数组一起工作：

[5, 3, 1, 8, 2, 4]

Answer 1

我写了蛮力算法，测试每一个可能的解决方案，并选出最好的。

用于下列问题集：

[5, 3, 1, 8, 2, 4]

它产生以下解决办法：

lowest cost: 72, with combination: [5, 4, 2, 8, 3, 1]

我们可以通过计算来证明：

5*1 + 4*2 + 2*3 + 8*4 + 3*5 + 1*6 = 72

这是解药者：

import java.util.*;

class ServersProblemSolver {
    public static void main(String[] args) {
        int[] serverDowntimes = {5, 3, 1, 8, 2, 4};

        int totalCost = Integer.MAX_VALUE;
        List<Integer> bestCombination = new ArrayList<>();

        for (int i = 0; i < Math.pow(2, serverDowntimes.length); i++) {
            int temporaryCost = 0;
            int combination = i;
            int start = 0;
            int end = serverDowntimes.length - 1;
            List<Integer> temporaryCombination = new ArrayList<>();

            for (int k = 0; k < serverDowntimes.length; k++) {
                if (combination % 2 == 1) {
                    temporaryCost += (k + 1) * serverDowntimes[start];
                    temporaryCombination.add(serverDowntimes[start]);
                    start++;
                } else {
                    temporaryCost += (k + 1) * serverDowntimes[end];
                    temporaryCombination.add(serverDowntimes[end]);
                    end--;
                }
                combination /= 2;
            }

            System.out.println("combination " + i + ": " + temporaryCombination + ", cost : " + temporaryCost);

            if (temporaryCost < totalCost) {
                totalCost = temporaryCost;
                bestCombination = temporaryCombination;
            } else {
                temporaryCombination.clear();
            }
        }

        System.out.println("lowest cost: " + totalCost + ", with combination: " + bestCombination);
    }
}

它怎麽工作?

• 以0和2 ^ N之间的每一个二进制组合为例，其中N是数组的大小。
• 根据继承二进制数字(无论是start还是1)从end或0中选择服务器
  • 101将带走start，end，start
  • 000将带走end，end，end
  • 110将带走end，start，start
  • 等。

​

• 在计算当前组合的结果之后，检查它是否优于以前的最佳组合，如果是的话，保存它。