Python 钢筋切割算法 - 变种

Question

我在课堂上被问到这个问题，作为一个脑筋急转弯，但我没能想出来（这不是作业问题，只是助教给我们思考的一个小挑战）。

你有一根杆子，给你一系列要切割的点，比如说 [1,5,11]，还有这根杆子的总长度，比如说 20。切割杆子的费用是根据杆子的长度来算的。我们的目标是找到在所有给定的切割点上切割这根杆子的最小费用，以及达到这个最小费用的切割顺序。

举个例子，如果你要在位置 5 切割一根长度为 20 的杆子，费用就是 $20，这样你会得到两段木头，一段长度为 5，另一段长度为 15。

再举个例子，如果你在长度为 25 的杆子上先在位置 5 切割，然后在位置 10 切割，第一次切割的费用是 $25，这样你会得到一段长度为 5 的木头和一段长度为 20 的木头，然后在位置 10 切割又要花 $20，总费用就是 $45。但是如果你先在位置 10 切割，再在位置 5 切割，费用就变成 $25 + $10 = $35。

最后，我们想要 返回在所有给定切割点上切割杆子的最小费用，以及达到这个最小费用的切割顺序。

我尝试为这个问题想出一个递归的解决方案，但一直没有头绪。有没有什么想法？任何帮助都很感激。谢谢！

Answer 1

为了解决这个问题，我们需要使用动态规划的方法。这是一种时间复杂度为O(n^3)的解决方案。（如果有人有更好的方法，请留言。）我们设定一个数组a[n+1][n+1]，其中n是杆子的长度。这个数组a[i][j]用来存储从位置i到位置j切割杆子的最小成本。我们有一个切割数组，里面包含了所有可以切割杆子的位置。对于每一段i到j的杆子，我们会考虑在切割数组中给出的所有k个位置进行切割，并找出最小的成本。我们会按照对角线的方式来填充这个数组。

#include <iostream>
#include <string.h>
#include <stdio.h>  
#include <limits.h>
using namespace std;
int main(){
   int i,j,gap,k,l,m,n;
   while(scanf("%d%d",&n,&k)!=EOF){

    int a[n+1][n+1];
    int cut[k];
    memset(a,0,sizeof(a));
    for(i=0;i<k;i++)
        cin >> cut[i];
    for(gap=1;gap<=n;gap++){
        for(i=0,j=i+gap;j<=n;j++,i++){
            if(gap==1)
                a[i][j]=0;
            else{
                int min = INT_MAX;
                for(m=0;m<k;m++){
                    if(cut[m]<j and cut[m] >i){
                        int cost=(j-i)+a[i][cut[m]]+a[cut[m]][j];

                        if(cost<min)
                            min=cost;
                    }
                }
                if(min>=INT_MAX)
                a[i][j]=0;
                else
                    a[i][j]=min;
            }
        }
    }
    cout << a[0][n] << endl;
}
return 0;
}

Answer 2

我认为，杆子切割问题的关键在于，贪心算法并不总是能得到最优解——这个变种似乎也证明了这一点。

想象一下，有一根长度为50的杆子，我们要在[13,25,26]的位置切割。如果我们选择离中间点最近的切割位置，算法会告诉我们选择[25, 13, 26]，这样总的成本是50 + 25 + 25 = 100。但我们可以通过选择[26, 13, 25]来改善这个结果，总成本变成了50 + 26 + 13 = 89。

补充说明：

也就是说，你会在L=50的杆子上选择在P=26的位置切割，这样就得到了一个L=24 (P=26->50)的杆子，这根杆子不需要再切割；还有一根L=26 (P=0->26)的杆子，需要在[25,13]的位置切割。接着，你在L=26的杆子上选择在P=13的位置切割，这样就得到了一个L=13 (P=0->13)的杆子，这根杆子也不需要再切割；还有一根L=13 (P=13->26)的杆子，需要在P=25的位置进行最后一次切割。最后一次切割的成本是每次切割的杆子长度之和（50 + 26 + 13）。

通常提出的替代方案是自上而下和自下而上的技术，这些方法的效率通常取决于所涉及的逻辑（对于传统的杆子切割问题，目标是最大化销售成本，自下而上的方法更受欢迎，因为它减少了递归调用）。