2

在我的一堂课上，我被问到这是一个脑筋急转弯，但我无法弄清楚（不是家庭作业问题，只是一个助教给我们思考的一个预告）。

给你一根棒子，上面有 n 个要切割的点，例如 [1,5,11]，棒子的总长度，例如 20。你还被告知切割一根棒子的费用是等价的到杆的长度。我们希望找到在所有给定切割下切割棒材的最低成本以及会导致最优成本的切割顺序。

例如，要在位置 5 处切割长度为 20 的杆，您将花费 20 美元，您最终会得到 2 根原木，一根长度为 5，一根长度为 15。

或者在另一个示例中，如果您在位置 5 切割长度为 25 的杆，然后在位置 10 切割，则在位置 5 切割它需要花费 25 美元，留下长度为 5 的杆和长度为 20 的杆，然后花费您在位置 10 再削减 20 美元，您在这两个位置的总成本为 45 美元。但是，如果您在位置 10 处切割杆，然后在位置 5 处切割，则将花费您 25 美元 + 10 美元 = 35 美元。

最后，我们想要return the minimum cost of cutting the rod at all the given cuts and the sequence of those cuts that would lead to the optimal cost.

我试图为这个问题提出一个递归解决方案，但一直空手而归。想法？任何帮助表示赞赏。谢谢！

4

2 回答 2

1

我相信棒切割问题的关键在于贪婪算法并不总是产生最佳解决方案 - 这个变体似乎证明了同一点。

考虑要在 处切割的 L=50 杆[13,25,26]。选择最接近中点的切割的算法会告诉你做[25, 13, 26]的总成本为50 + 25 + 25 = 100. 我们可以通过[26, 13, 25]花费50 + 26 + 13 = 89.

编辑：

IE。您将在 处切割一根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)。

通常提出的替代方案是自上而下和自下而上的技术，这些技术的效率通常取决于所涉及的逻辑（对于试图最大化销售成本的传统棒材切割问题，自下而上是首选，因为它减少了递归来电）。

于 2013-02-05T04:12:54.093 回答
0

为了解决这个问题，您必须使用动态编程方法。这是一个基于 O(n^3) 的解决方案。（如果有人有更好的解决方案，请发表评论）。让我们有一个数组 a[n+1][n+1]，其中 n= 棒的长度。a[i][j] 将存储将杆从位置 i 切割到位置 j 的最小成本。我们得到一个切割数组，其中包含切割棒的所有位置。对于每个 ij 杆，我们考虑将其切割为切割数组中给出的所有 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;
}
于 2015-11-16T15:30:46.633 回答