java - 找到最小的总服务器停机时间

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]

它生成以下解决方案:

最低成本:72，组合:[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 是数组的大小。
• 根据连续的二进制数字(无论是0还是1)从start或end选择服务器
  • 101 将占用 start、end、start
  • 000 将占用 end、end、end
  • 110 将占用 end、start、start
  • 等等
• 计算出当前组合的结果后，检查是否比之前最好的更好，如果是，则保存。