Python棒切割算法 - 变体

我被问到这是在我的一个课程中的脑筋急转弯，但无法弄清楚（这不是一个家庭作业问题，只是TA的一个让我们思考的传情）。Python棒切割算法 - 变体

给你一个带有n个切点列表的棒，例如[1,5,11]和棒的总长度，例如20。你也被告知切割费用一根杆相当于杆的长度。我们希望在所有给定的切割中找到切割棒的最低成本，以及那些会导致最佳成本的切割顺序。

例如，切割长度为20的杆在位置5处，这将花费您$ 20时最终会与2个日志，一个长度为5和一个长度为15

或者在另一示例，如果你在位置5切割长度为25的棒，然后在位置10切割，那么在位置5切割它需要花费25美元，留下长度为5的棒和长度为20的棒，然后花费你20美元到在10号位切割它，让你在两个位置切割的总成本为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.

我试图想出了这个问题的递归解决方案，但保留未来两手空空。思考？任何帮助表示赞赏。谢谢！

来源

2013-02-05 user1530318

如果这是一个家庭作业的问题，你应该将其标记为这样的人会帮助你走向解决方案，只要你证明你已经尝试 – bcoughlan

@bcoughlan - 作业标记已被弃用。但是，关于展示企图代码的观点非常感谢。 – mgilson

我什至不能找出一个算法来做到这一点....更不用说一些代码 – user1530318

我相信杆切割问题的重点在于贪婪算法并不总能产生最佳解决方案 - 这种变体似乎证明了相同点。

考虑将L = 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）。

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

来源

2013-02-05 04:12:54

不会[26,13,25]是50 + 24 + 26 = 100还是？ – user1530318

在那种情况下，你什么时候要切割L = 24的棒？一会儿，我在答案中澄清了这个过程。 –

您可以使用递归来遍历调用树，并将最佳（子）路径的累积成本备份。每个路径的公共部分可以节省一倍。 –

为了解决这个问题，你必须使用动态规划方法。这是一个基于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; 
}

来源

2015-11-16 15:30:46

Python棒切割算法 - 变体

回答

相关问题