SCL编程实例100例-120-贪心算法解决剪绳子问题

1 | 题目

把长度为n的绳子剪成m段（n>1，m>1），每段绳子的长度记为k[1]、k[2]、...、k[m]，求剪切后的各段绳子的长度的最大乘积是多少？例如：绳子长度为8时，剪成2、3、3三段得到的乘积最大，值为18。



2 | 设计分析

尽可能将绳子以长度3等分为多段时，乘积最大。

剪切原则：
最优3：把绳子尽可能剪切为多个长度为3的片段，留下最后一段绳子的长度可能为0、1、2三种情况。
次优2：若最后一段绳子长度为2，则保留，不再拆分为1+1。
最差1：若最后一段绳子长度为1，则应把一份3+1替换为2+2，因为2*2>3*1。



3 | 创建功能或功能块

创建功能块FB，命名为“CutRopeGreedy”。




4 | 定义接口变量

具体接口变量定义见下图：

定义整型输入变量length，绳子的长度；
定义整型输出变量result，剪切后各段乘积的最大值；
定义整型静态变量statNumOf3，以长度3等分的取整段数。



5 | 程序代码

编写程序代码。如下图：

绳子长度分别为1、2、3、4时根据推论结果直接输出并返回。利用FOR循环求各段乘积，循环次数为3的段数，然后乘以剪切剩余的长度值。



6 | 代码测试

在循环OB中调用FB-“CutRopeGreedy”，调用时会自动创建背景数据块，命名为“InstCutRopeGreedy”，该背景数据块可以用来监视和修改数据。转至在线并监控程序。如下图：

输入绳子的长度8，得到各段的乘积最大值为18。



7 | 总结

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！