写 一维下料 套料 算法 c++代码

admin

这段代码实现了基于递归的回溯算法，用于计算一维下料套料问题的切割方案。输入为待切割的材料列表和目标长度，输出为所有满足条件的切割方案。

具体实现思路如下：

首先定义了两个结构体：Material表示材料，包含长度和编号；CutPlan表示切割方案，包含所有切割后的材料、总长度和材料数量。
实现了一个比较函数compareMaterials，用于对材料按长度进行排序。
实现了一个递归函数recursiveCutting，用于计算切割方案。该函数接收切割方案、材料列表、起始位置和剩余长度作为参数。当剩余长度为0时，表示找到了一种切割方案，更新切割方案的总长度和材料数量。否则，遍历所有可能的切割位置，将符合条件的材料加入切割方案，并递归调用自身切割剩余部分。最后，通过回溯撤销上一步操作。
实现了主函数calculateCutPlans，用于计算一维下料套料算法的切割方案。首先对材料按长度进行排序，然后生成切割方案。通过调用递归函数recursiveCutting生成切割方案，并将满足条件的切割方案加入结果列表。
在主函数中，给定了一个测试样例，计算了切割方案，并输出了结果。
这段代码可以计算出所有满足条件的切割方案，并输出切割方案的总长度、材料数量和材料列表。

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
5. // 定义材料结构体
6. struct Material {
7.     int length;
8.     int id;
9. };
11. // 定义切割方案结构体
12. struct CutPlan {
13.     std::vector<Material> materials;
14.     int totalLength;
15.     int numMaterials;
16. };
18. // 比较两个材料的长度
19. bool compareMaterials(const Material& m1, const Material& m2) {
20.     return m1.length < m2.length;
21. }
23. // 递归函数，计算切割方案
24. void recursiveCutting(CutPlan& plan, std::vector<Material>& materials, int startIndex, int remainingLength) {
25.     // 当剩余长度为0时，表示找到了一种切割方案
26.     if (remainingLength == 0) {
27.         plan.totalLength += materials[startIndex].length;
28.         plan.numMaterials++;
29.         return;
30.     }
32.     // 遍历所有可能的切割位置
33.     for (int i = startIndex; i < materials.size(); i++) {
34.         // 当前切割位置的材料长度小于等于剩余长度
35.         if (materials[i].length <= remainingLength) {
36.             // 更新切割方案
37.             plan.materials.push采用back(materials[i]);
38.             plan.totalLength += materials[i].length;
39.             plan.numMaterials++;
41.             // 递归调用，继续切割剩余部分
42.             recursiveCutting(plan, materials, i + 1, remainingLength - materials[i].length);
44.             // 回溯，撤销上一步操作
45.             plan.totalLength -= materials[i].length;
46.             plan.numMaterials--;
47.         }
48.     }
49. }
51. // 计算一维下料套料算法的切割方案
52. std::vector<CutPlan> calculateCutPlans(const std::vector<Material>& materials, int targetLength) {
53.     std::vector<CutPlan> plans;
55.     // 对材料按长度进行排序
56.     std::vector<Material> sortedMaterials = materials;
57.     std::sort(sortedMaterials.begin(), sortedMaterials.end(), compareMaterials);
59.     // 生成切割方案
60.     CutPlan plan;
61.     plan.totalLength = 0;
62.     plan.numMaterials = 0;
63.     for (int i = 0; i < sortedMaterials.size(); i++) {
64.         plan.materials.clear();
65.         recursiveCutting(plan, sortedMaterials, i, targetLength);
66.         if (plan.totalLength == targetLength && plan.numMaterials > 0) {
67.             plans.push采用back(plan);
68.         }
69.     }
71.     return plans;
72. }
74. int main() {
75.     // 测试样例
76.     std::vector<Material> materials = {
77.         {5, 1},
78.         {3, 2},
79.         {4, 3},
80.         {2, 4},
81.         {6, 5}
82.     };
85.                 std::vector<Material> materials;
87.                 Material a1;
88.                 a1.id=1;
89.                 a1.length=5;
90.                 materials.push采用back(a1);
92.                 a1.id=2;
93.                 a1.length=3;
94.                 materials.push采用back(a1);
96.                 a1.id=3;
97.                 a1.length=4;
98.                 materials.push采用back(a1);
100.                 a1.id=4;
101.                 a1.length=2;
102.                 materials.push采用back(a1);
104.                 a1.id=5;
105.                 a1.length=6;
106.                 materials.push采用back(a1);
109.     int targetLength = 10;
111.     // 计算切割方案
112.     std::vector<CutPlan> plans = calculateCutPlans(materials, targetLength);
114.     // 输出切割方案
115.     std::cout << "Number of cut plans: " << plans.size() << std::endl;
116.     for (int i = 0; i < plans.size(); i++) {
117.         std::cout << "Cut plan " << i + 1 << ":" << std::endl;
118.         std::cout << "Total length: " << plans[i].totalLength << std::endl;
119.         std::cout << "Number of materials: " << plans[i].numMaterials << std::endl;
120.         std::cout << "Materials:" << std::endl;
121.         for (int j = 0; j < plans[i].materials.size(); j++) {
122.             std::cout << plans[i].materials[j].length << " (id: " << plans[i].materials[j].id << ")" << std::endl;
123.         }
124.         std::cout << std::endl;
125.     }
127.     return 0;
128. }

复制代码