C++ 连接木棍的最小成本

2025年3月21日 | 阅读 9 分钟

“连接木棍的最小成本”问题是一个常见的算法任务，其中需要将多个木棍元素合并成一根，成本等于两个连接木棍的长度之和。目标是降低连接所有木棍的总成本。该问题可以与哈夫曼编码问题相比较，即先处理小元素可以获得更低的成本。

在这个问题中，您的木棍长度给在一个数组中，所以每次连接两根木棍时，它们的合并长度会加到总成本中。连接木棍的最佳策略始终是在每一步连接两根最短的木棍，这样可以在初始阶段就产生较小的成本。

使用最小堆或优先队列的贪心算法是解决该问题的一种有效方法。最小堆有助于在每一步高效地选择两根最短的木棍，从而确保组合成本最小化。该策略的时间复杂度为 O(n log n)。

方法 1：暴力方法

解决上述“连接木棍最小成本”问题的最简单方法是直接方法，即尝试连接木棍的所有可能性，并计算按每种可能组合顺序的总成本。虽然这种方法确保您获得最可行的成本，但效率低下，因为细分数量会随着木棍数量的增加呈指数级增长。这使得处理大型输入变得困难，尤其是在测量值很大时。

您会得到一个木棍长度的列表，您必须将所有这些木棍连接成一根总木棍。每次将两根木棍放在一起时，连接两根木棍的成本是木棍长度的总和，并且此成本会累积。因此，总成本成为这两个变量的总和。目标是降低此总成本。

示例

让我们通过一个例子来说明如何使用 C++ 中的暴力方法找到连接木棍的最小成本。

 
#include <iostream>
#include <vector>
#include <climits>  // For INT_MAX to represent infinity
#include <algorithm> // For std::min
// Utility function to print a vector of sticks (for debugging purposes)
void printSticks(const std::vector<int>& sticks) {
    std::cout << "Current sticks: ";
    for (int stick : sticks) {
        std::cout << stick << " ";
    }
    std::cout << std::endl;
}
// Recursive function to calculate the minimum cost of connecting sticks
int minCostToConnectSticks(std::vector<int> sticks) {
    // Base case: If there is only one stick left, no more connections are needed
    if (sticks.size() == 1) {
        return 0;  // No cost required to connect one stick
    }
    int minTotalCost = INT_MAX;  // Initialize the minimum total cost to a large value (infinity)
    // Nested loop to try every possible pair of sticks to combine
    for (size_t i = 0; i < sticks.size(); i++) {
        for (size_t j = i + 1; j < sticks.size(); j++) {            
            // Step 1: Combine the two sticks at indices i and j
            int combinedCost = sticks[i] + sticks[j]; // Cost to combine the two sticks
            std::cout << "Combining sticks " << sticks[i] << " and " << sticks[j] << " with cost " << combinedCost << std::endl;            
            // Step 2: Create a new vector (newSticks) after combining sticks[i] and sticks[j]
            std::vector<int> newSticks;            
            // Add the combined stick (the result of combining sticks[i] and sticks[j])
            newSticks.push_back(combinedCost);         
            // Add the remaining sticks to the new vector (excluding sticks[i] and sticks[j])
            for (size_t k = 0; k < sticks.size(); k++) {
                if (k != i && k != j) {
                    newSticks.push_back(sticks[k]);
                }
            }      
            // Step 3: Recursively calculate the cost to connect the remaining sticks
            int currentCost = combinedCost + minCostToConnectSticks(newSticks);   
            // Step 4: Track the minimum total cost of all possible combinations
            minTotalCost = std::min(minTotalCost, currentCost);    
            // Print the current stick configuration and the current cost for debugging
            std::cout << "After combining, new configuration: ";
            printSticks(newSticks);
            std::cout << "Current total cost: " << currentCost << std::endl;
            std::cout << "--------------------------------" << std::endl;
        }
    } 
    // Return the minimum total cost of connecting all the sticks
    return minTotalCost;
}
int main() {
    // Example 1: A simple case with three sticks
    std::vector<int> sticks = {1,2,3};
    // Print the initial sticks configuration
    std::cout << "Initial sticks: ";
    printSticks(sticks);  
    // Calculate and print the minimum cost to connect all sticks
    int result = minCostToConnectSticks(sticks);
    std::cout << "Minimum cost to connect all sticks: " << result << std::endl;
    std::cout << "=================================" << std::endl;
    // Example 2: A more complex case with five sticks
    std::vector<int> sticks2 = {4, 3}; 
    // Print the initial sticks configuration
    std::cout << "Initial sticks: ";
    printSticks(sticks2); 
    // Calculate and print the minimum cost to connect all sticks
    int result2 = minCostToConnectSticks(sticks2);
    std::cout << "Minimum cost to connect all sticks: " << result2 << std::endl;
    return 0;
}   

输出

 
Initial sticks: Current sticks: 1 2 3 
Combining sticks 1 and 2 with cost 3
Combining sticks 3 and 3 with cost 6
After combining, new configuration: Current sticks: 6 
Current total cost: 6
--------------------------------
After combining, new configuration: Current sticks: 3 3 
Current total cost: 9
--------------------------------
Combining sticks 1 and 3 with cost 4
Combining sticks 4 and 2 with cost 6
After combining, new configuration: Current sticks: 6 
Current total cost: 6
--------------------------------
After combining, new configuration: Current sticks: 4 2 
Current total cost: 10
--------------------------------
Combining sticks 2 and 3 with cost 5
Combining sticks 5 and 1 with cost 6
After combining, new configuration: Current sticks: 6 
Current total cost: 6
--------------------------------
After combining, new configuration: Current sticks: 5 1 
Current total cost: 11
--------------------------------
Minimum cost to connect all sticks: 9
=================================
Initial sticks: Current sticks: 4 3 
Combining sticks 4 and 3 with cost 7

说明

这个 C++ 程序通过将所有木棍首尾相连地连接成一根大木棍来实现。所有组合成本都等于正在组合的两根木棍长度的总和。问题是如何最小化连接所有木棍的总成本。

1. 输入表示

该程序处理一个整数数组（或向量），其中每个元素都对应于每根木棍的长度。例如，对于形式为数组的输入，即 [1, 2, 3]，这意味着有三根长度分别为 1、2 和 3 的木棍。为了得到这个解决方案，程序需要找出以何种成本可以将所有这些木棍连接成一根单一木棍。

2. 递归函数 (minCostToConnectSticks)

主要控制由完整的 minCostToConnectSticks 函数负责，该函数接受一个整数向量和木棍。该函数以迭代方式工作，选择并考虑所有可能的木棍对，然后计算剩余木棍的最小成本。

基本情况

当向量中只剩下一根木棍时，就出现了基本情况。在这种情况下，不再需要进行组合，因此函数返回 0 的成本。这是递归的终结，因为最终的分解将产生一个单一值，但问题是如何在不使用递归的情况下获得数字的根？

递归情况

对于递归情况，函数会遍历木棍的所有可能性，这通过两个嵌套循环来实现。它首先计算将两根木棍连接起来形成一根新木棍的成本，然后创建一个包含新形成的木棍以及未连接的其他所有木棍的新木棍向量。

在确定了当前木棍对的连接成本后，函数会继续递归地处理新形成的木棍和剩余的木棍，从而保持一种高效的策略来最小化总成本。

总成本定义为当前组合成本与递归调用剩余木棍的函数后获得的成本之和。

在每次递归步骤中，当前组合成本都会与迄今为止找到的最小成本进行比较，从而确保找到最优解。

3. 木棍组合

在 minCostToConnectSticks 中，该函数通过检查每对木棍并计算使用其长度组合它们的成本来评估所有可能的木棍组合。

组合后的木棍最终会被追加到一个新向量中，该向量包含木棍，然后将此向量传递给递归调用。将原始的两根木棍重新组合到新向量中并不重要，因此它们被移除了。

对于组合的每对木棍，函数会重新计算总成本，并递归地继续组合下一组木棍，确保探索所有可能的组合，直到只剩下最终木棍。

通过这种方式，函数在每一步递归处理下一个木棍时，都会尝试所有可能的组合。

4. 跟踪最小成本

问题中的目标是确定产生最小总成本的组合顺序。在连接两根木棍的每次连接中，函数都会将连接成本附加到总和中，并且函数会继续要求两根木棍，直到完成。

变量 minTotalCost 被初始化为一个很大的值 (INT_MAX)，并在每次递归调用中用最小的总成本进行更新，从而确保在整个过程中跟踪最小成本。

提到了 minTotalCost 变量，该变量在每次递归调用完成后都会更新。此变量存储了针对特定数量的木棍以特定方式处理所找到的最小总数。当所有递归调用都执行完毕后，minTotalCost 变量将包含连接给定木棍可以花费的最小总成本。

5. 实用函数 (printSticks)

辅助函数 printSticks 可视化地显示每对木棍组合后的当前状态，有助于在每个阶段跟踪进度和成本。

该函数在一对木棍连接后调用，以显示剩余的木棍以及在该阶段的连接成本。

6. 主函数 (main)

主函数提供了两个案例来测试程序。以下是这些案例的简要描述：在第一个示例中，木棍长度为 {1, 2, 3}，而在第二个示例中，木棍长度为 {4, 3}。

对于每个示例，程序：

在 printSticks 的帮助下输出木棍的第一个图示。
它调用 minCostToConnectSticks 来计算连接所有木棍的最小成本。
它打印出结果，即最小的运输成本。

7. 输出

程序打印中间步骤，包括正在组合的木棍及其相关成本，并输出连接所有木棍所需的最小成本。

复杂度分析

时间复杂度

C++ 代码中使用的这种暴力方法具有 **阶乘时间复杂度 O(n!)，其中 'n' 是木棍的数量。
minCostToConnectSticks 函数通过考虑每对木棍并将它们融合在一起。每次函数调用自身时，系统都会尝试将每根木棍组合在一起，由于内部循环尝试所有对，因此需要 'O(n^2)' 的时间。
这个迭代函数按顺序组合两个获得的木棍，从而创建一个比原来少一根木棍的新向量。之后，该过程对剩余的 'n-1' 根木棍保持递归。这导致时间复杂度为 O(n!)，因为它会探索所有可能的组合方式。
这意味着随着木棍数量的增加，可达到的结果总数会急剧增加，以至于当输入很大时，使用暴力方法会变得不切实际。

空间复杂度

上述问题的最坏情况时间复杂度可以是 O(n^2)，空间复杂度也变为 O(n^2)。
递归深度：该函数是递归的，每次函数调用时，木棍的数量会减少一。因此，最大递归深度为 'n'，并且由于函数调用堆栈，它会增加 O(n) 的时间复杂度（空间复杂度）。
新木棍向量创建：在递归的每个级别，都会生成一个大小为 'n-1' 的新木棍向量。由于在每次递归步骤中都会创建新的向量，并且复制它们需要 O(n)，因此复制所需的总时间为 O(n^2)。
因此，在空间复杂度方面，存在递归深度以及每个递归调用中创建的多个新向量，这意味着存在 O(n^2) 的空间复杂度。

下一个主题C++ 中的 FIFO 推送重标记算法

C++ 连接木棍的最小成本

方法 1：暴力方法

示例