本文主要是介绍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算法:把一块木板切成正方形的最低成本—贪心算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!