算法:把一块木板切成正方形的最低成本—贪心算法"/>
JAVA算法:把一块木板切成正方形的最低成本—贪心算法
JAVA算法:把一块木板切成正方形的最低成本—动态规划
给出了一块长度为m宽度为n的木板,需要把这个木板分解成m*n的正方形,这样就可以把破坏的成本降到最低。
每边的切割成本将为板提供。简言之,我们需要选择这样一个切割的顺序,以使成本最小化。
对于上述板,切割成正方形的最佳方法是:最低总成本为42。
使用以下步骤:
Initial Value : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces
成本4水平切割成本=0+4*1=4
成本4垂直切割成本=4+4*2=12
成本3垂直切割成本=12+3*2=18
成本2水平切割成本=18+2*3=24
成本2垂直切割成本=24+2*3=30
成本1水平切割成本=30+1*4=34
成本1垂直切割成本=34+1*4=38
成本1垂直切割成本=38+1*4=42
问题分析:
这个问题可以用贪心算法来解决。
更多推荐
JAVA算法:把一块木板切成正方形的最低成本—贪心算法
发布评论