绳子切割优化难题（一维下料）

20060510412

求助！绳子切割优化难题（一维下料），看看大佬们有没有好解法？
各位大神，最近遇到一个超烧脑的绳子切割问题，研究好久也没想到特别好的解决办法，来论坛求助，希望大家帮忙出出主意！
问题描述有一根长度固定的绳子，需要将其切割成 N 段，具体要求如下：

• 中间段：中间的绳子长度必须为标准长度，包括 2m、3m、4m、5m、6m，这些标准长度可以自由组合。
• 两端段：绳子两端的长度必须相同，长度范围在 1.5m - 3.5m 之间，并且可以是非标准长度。
• 布局要求：整体布局要符合中间部分长、两端部分短的原则，并且尽量对称。
• 切割目标：在满足以上所有条件的情况下，切割后的绳子段数 N 要尽可能少。
  

举例说明假设绳子长度为 14m，一种可能的切割方案是：2m | 5m | 5m | 2m ，总共 4 段，这个方案就满足两端长度相同且在规定范围内、中间为标准长度、中间长两端短且对称，同时也尽量让段数少。但如果绳子长度变化，可能就需要重新规划切割方式。
求助需求目前我尝试了一些思路，但效果都不太理想，想问问大家：

• 这个问题有没有比较经典的算法或模型可以套用？
• 如果自己编写代码解决，从哪个方向入手比较合适？
• 大家有没有类似问题的解决经验可以分享？
  

无论是完整的解决方案、算法思路，还是一段参考代码，都欢迎在评论区分享！提前感谢各位大佬的帮助

自贡黄明儒

数n,先减去2*6，比较余数是否在 1.5m - 3.5m 之间；如果小于1.5m，就减去先减去2*5.....

mahuan1279

暴力枚举不是难事。1.5*2<=N-2*2K1-3*2K2-4*2K3-5*2K4-6*K5<=3.5*2,求ΣKi最小

20060510412

mahuan1279 发表于 2025-6-26 11:26
暴力枚举不是难事。1.5*2

暴力枚举，如果总长度接近100的话，需要的时间就很长了。

对算法不是很懂，像这种一维下料的问题，是不是要用到动态规划、遗传算法之类的算法，才能比较高效解决问题呢？

你有种再说一遍

这种问题不是入门就有了吗?叫动态规划,去刷刷力扣就知道了.
而且你描述那么好了,直接问AI,生成个py代码验证

mahuan1279

20060510412 发表于 2025-6-26 12:57
暴力枚举，如果总长度接近100的话，需要的时间就很长了。

对算法不是很懂，像这种一维下料的问题，是 ...

从长到短进行贪心算法……

20060510412

你有种再说一遍 发表于 2025-6-26 13:20
这种问题不是入门就有了吗?叫动态规划,去刷刷力扣就知道了.
而且你描述那么好了,直接问AI,生成个py代码验 ...

我是好奇，目前有没有已经造好的轮子可以直接用的呢？
例如已经造好了相关函数，输入绳子的总长度，直接输出绳子的最优切割方案。
应该是有的吧？

mahuan1279

20060510412 发表于 2025-6-26 21:05
我是好奇，目前有没有已经造好的轮子可以直接用的呢？
例如已经造好了相关函数，输入绳子的总长度，直接 ...

我们不编写代码，只是代码的搬运工……

xyp1964

7 : (1.5 2 2 1.5)
8 : (2 2 2 2)
9 : (1.5 3 3 1.5)
10 : (2 3 3 2)
11 : (1.5 4 4 1.5)
12 : (2 4 4 2)
13 : (1.5 5 5 1.5)
14 : (2 5 5 2)
15 : (1.5 6 6 1.5)
16 : (2 6 6 2)
17 : (2.5 6 6 2.5)
18 : (3 6 6 3)
19 : (3.5 6 6 3.5)
20 : (2 2 6 6 2 2)
21 : (1.5 3 6 6 3 1.5)
22 : (2 3 6 6 3 2)
23 : (1.5 4 6 6 4 1.5)
24 : (2 4 6 6 4 2)
25 : (1.5 5 6 6 5 1.5)
26 : (2 5 6 6 5 2)
27 : (1.5 6 6 6 6 1.5)
28 : (2 6 6 6 6 2)
29 : (2.5 6 6 6 6 2.5)
30 : (3 6 6 6 6 3)
31 : (3.5 6 6 6 6 3.5)
32 : (2 2 6 6 6 6 2 2)
33 : (1.5 3 6 6 6 6 3 1.5)
34 : (2 3 6 6 6 6 3 2)
35 : (1.5 4 6 6 6 6 4 1.5)
36 : (2 4 6 6 6 6 4 2)
37 : (1.5 5 6 6 6 6 5 1.5)
38 : (2 5 6 6 6 6 5 2)
39 : (1.5 6 6 6 6 6 6 1.5)
40 : (2 6 6 6 6 6 6 2)
41 : (2.5 6 6 6 6 6 6 2.5)
42 : (3 6 6 6 6 6 6 3)
43 : (3.5 6 6 6 6 6 6 3.5)
44 : (2 2 6 6 6 6 6 6 2 2)
45 : (1.5 3 6 6 6 6 6 6 3 1.5)
46 : (2 3 6 6 6 6 6 6 3 2)
47 : (1.5 4 6 6 6 6 6 6 4 1.5)
48 : (2 4 6 6 6 6 6 6 4 2)
49 : (1.5 5 6 6 6 6 6 6 5 1.5)
50 : (2 5 6 6 6 6 6 6 5 2)
51 : (1.5 6 6 6 6 6 6 6 6 1.5)
52 : (2 6 6 6 6 6 6 6 6 2)
53 : (2.5 6 6 6 6 6 6 6 6 2.5)
54 : (3 6 6 6 6 6 6 6 6 3)
55 : (3.5 6 6 6 6 6 6 6 6 3.5)
56 : (2 2 6 6 6 6 6 6 6 6 2 2)
57 : (1.5 3 6 6 6 6 6 6 6 6 3 1.5)
58 : (2 3 6 6 6 6 6 6 6 6 3 2)
59 : (1.5 4 6 6 6 6 6 6 6 6 4 1.5)
60 : (2 4 6 6 6 6 6 6 6 6 4 2)
61 : (1.5 5 6 6 6 6 6 6 6 6 5 1.5)
62 : (2 5 6 6 6 6 6 6 6 6 5 2)
63 : (1.5 6 6 6 6 6 6 6 6 6 6 1.5)
64 : (2 6 6 6 6 6 6 6 6 6 6 2)
65 : (2.5 6 6 6 6 6 6 6 6 6 6 2.5)
66 : (3 6 6 6 6 6 6 6 6 6 6 3)
67 : (3.5 6 6 6 6 6 6 6 6 6 6 3.5)
68 : (2 2 6 6 6 6 6 6 6 6 6 6 2 2)
69 : (1.5 3 6 6 6 6 6 6 6 6 6 6 3 1.5)
70 : (2 3 6 6 6 6 6 6 6 6 6 6 3 2)
71 : (1.5 4 6 6 6 6 6 6 6 6 6 6 4 1.5)
72 : (2 4 6 6 6 6 6 6 6 6 6 6 4 2)
73 : (1.5 5 6 6 6 6 6 6 6 6 6 6 5 1.5)
74 : (2 5 6 6 6 6 6 6 6 6 6 6 5 2)
75 : (1.5 6 6 6 6 6 6 6 6 6 6 6 6 1.5)
76 : (2 6 6 6 6 6 6 6 6 6 6 6 6 2)
77 : (2.5 6 6 6 6 6 6 6 6 6 6 6 6 2.5)
78 : (3 6 6 6 6 6 6 6 6 6 6 6 6 3)
79 : (3.5 6 6 6 6 6 6 6 6 6 6 6 6 3.5)
80 : (2 2 6 6 6 6 6 6 6 6 6 6 6 6 2 2)
81 : (1.5 3 6 6 6 6 6 6 6 6 6 6 6 6 3 1.5)
82 : (2 3 6 6 6 6 6 6 6 6 6 6 6 6 3 2)
83 : (1.5 4 6 6 6 6 6 6 6 6 6 6 6 6 4 1.5)
84 : (2 4 6 6 6 6 6 6 6 6 6 6 6 6 4 2)
85 : (1.5 5 6 6 6 6 6 6 6 6 6 6 6 6 5 1.5)
86 : (2 5 6 6 6 6 6 6 6 6 6 6 6 6 5 2)
87 : (1.5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 1.5)
88 : (2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 2)
89 : (2.5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 2.5)
90 : (3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 3)
91 : (3.5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 3.5)
92 : (2 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 2 2)
93 : (1.5 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 3 1.5)
94 : (2 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 3 2)
95 : (1.5 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 1.5)
96 : (2 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 2)
97 : (1.5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 5 1.5)
98 : (2 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 5 2)
99 : (1.5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 1.5)
100 : (2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 2)

20060510412

xyp1964 发表于 2025-6-26 23:42
7 : (1.5 2 2 1.5)
8 : (2 2 2 2)
9 : (1.5 3 3 1.5)

请问这是不是贪心算法？
先采用最符合当前的方案，也就是先考虑最长的段。