当前位置: 首页 > article >正文

一维下料之 *贪心算法* —— CAD c#二次开发

一维下料之贪心算法,需求如下

已知条件
我们有一批长度为 380 米 的原材料(例如钢管、木材等)。
切割需求
需要从这些原材料中切割出以下长度的小段:42 米:需要 13 段
140米:需要 23 段
130 米:需要 12 段

120 米:需要 12 段
11 米:需要 2 段
234米:需要 12 段
问题需求

我们的目标是:
用尽可能少的原材料(总根数最少),切割出所有需要的小段,同时尽可能减少浪费(即原材料的剩余长度总和最小)。

结果如下: 

贪心算法: 使用原材料 26 个,总剩余 830 米,利用率 91.60%

原材料 1: [234, 140] 剩余: 6 米
原材料 2: [234, 140] 剩余: 6 米
原材料 3: [234, 140] 剩余: 6 米
原材料 4: [234, 140] 剩余: 6 米
原材料 5: [234, 140] 剩余: 6 米
原材料 6: [234, 140] 剩余: 6 米
原材料 7: [234, 140] 剩余: 6 米
原材料 8: [234, 140] 剩余: 6 米
原材料 9: [234, 140] 剩余: 6 米
原材料 10: [234, 140] 剩余: 6 米
原材料 11: [234, 140] 剩余: 6 米
原材料 12: [234, 140] 剩余: 6 米
原材料 13: [140, 140, 11, 11] 剩余: 78 米
原材料 14: [140, 140] 剩余: 100 米
原材料 15: [140, 140] 剩余: 100 米
原材料 16: [140, 140] 剩余: 100 米
原材料 17: [140, 140] 剩余: 100 米
原材料 18: [140, 130] 剩余: 110 米
原材料 19: [130, 130, 120] 剩余: 0 米
原材料 20: [130, 130, 120] 剩余: 0 米
原材料 21: [130, 130, 120] 剩余: 0 米
原材料 22: [130, 130, 120] 剩余: 0 米
原材料 23: [130, 130, 120] 剩余: 0 米
原材料 24: [130, 120, 120] 剩余: 10 米
原材料 25: [120, 120, 120] 剩余: 20 米
原材料 26: [120, 120] 剩余: 140 米

部分源代码如下

public class 一维下料
{
    // 定义原材料长度
    private const int 原材料长度 =380;

    // 定义需要的切割长度及其数量
    private static readonly Dictionary<int, int> 需求长度 = new Dictionary<int, int>
    {
         { 140, 23 }, { 130, 12 }, { 120, 12 }, { 11, 2 }, { 234, 12 }
    };
    [CommandMethod("xx")]
    public static void 一维下料贪心算法()
    {
        // 获取切割方案、剩余长度和利用率
        List<int> 剩余长度s;
        double 利用率;
        List<List<int>> 切割计划s = 计算剩余长度s和利用率(out 剩余长度s, out 利用率);

        // 输出切割方案
        Env.Editor.WriteMessage("切割方案:\n");
        int 最终原材料个数 = 0;
        for (int i = 0; i < 切割计划s.Count; i++)
        {
            Env.Editor.WriteMessage($"原材料 {i + 1}: [{ string.Join(", ", 切割计划s[i]) } ](剩余长度: {剩余长度s[i]} 米)\n");
            最终原材料个数 = i + 1;
        }

        // 输出总剩余长度
        int 总剩余长度 = 剩余长度s.Sum();
        Env.Editor.WriteMessage($"共需要{最终原材料个数}个原材料,总剩余长度: {总剩余长度} 米\n");

        // 输出利用率
        Env.Editor.WriteMessage($"贪心算法利用率: {利用率:F2}%\n");

        // 验证是否所有需要的长度都被切割
        bool allCut = true;
        foreach (var length in 需求长度.Keys)
        {
            if (需求长度[length] > 0)
            {
                allCut = false;
                break;
            }
        }

        Env.Editor.WriteMessage(allCut ? "所有长度都已切割完毕。" : "部分长度未切割完毕。\n");
    }
    // 贪心算法实现
    public static List<List<int>> 计算剩余长度s和利用率(out List<int> 剩余长度s, out double 利用率)
    {
        // 存储最终的切割方案
        List<List<int>> 切割计划s = new List<List<int>>();

        // 存储每根原材料的剩余长度
        剩余长度s = new List<int>();

        // 复制需要的切割长度及其数量,避免修改原始数据
        Dictionary<int, int> requiredLengthsCopy = new Dictionary<int, int>(需求长度);

        // 总使用的材料长度
        int 总使用长度 = 0;

        // 循环直到所有需要的长度都被切割
        while (true)
        {
            // 当前原材料的剩余长度
            int 当前材料剩余长度 = 原材料长度;

            // 当前原材料的切割方案
            List<int> 最终方案 = new List<int>();

            // 从最长的长度开始尝试切割
            foreach (var length in requiredLengthsCopy.Keys.ToList())
            {
               /*****************省略部分源代码***********************/
            }

            // 如果当前原材料没有切割任何长度,则退出循环
            if (最终方案.Count == 0)
                break;

            // 将当前切割方案添加到最终方案中
            切割计划s.Add(最终方案);

            // 记录当前原材料的剩余长度
            剩余长度s.Add(当前材料剩余长度);
        }

        // 计算利用率
        int total原材料长度 = 切割计划s.Count * 原材料长度; // 总原材料长度
        利用率 = (double)总使用长度 / total原材料长度 * 100; // 利用率百分比

        return 切割计划s;
    }

}


http://www.kler.cn/a/583714.html

相关文章:

  • 【软考-架构】3.3、模式分解-事务并发-封锁协议
  • C# WPF 基础知识学习(一)
  • 贪心算法(5)(java)k次取反后最大化的数组和
  • 什么是AI?AI能对我们生活产生哪些影响?
  • LeetCode 112. 路径总和 II java题解
  • 如何用Docker容器化Java应用?Spring Boot实战指南
  • Spring Boot 约定大于配置:实现自定义配置
  • HCIP复习拓扑练习(修改版)
  • 【3DGS】SuperSplat本地运行+修改监听端口+导入ply模型+修剪模型+在线渲染3DGS网站推荐
  • 设计模式C++
  • Java 8新特性:Lambda表达式与Stream API实战
  • OEM SQL Details and Session Details 5s 或者parallel 才会在sql monitor显示
  • Aliyun CTF 2025 web 复现
  • uniapp,自绘仪表盘组件(基础篇)
  • BEVDepth: Acquisition of Reliable Depth for Multi-view 3D Object Detection 论文阅读
  • c# txt文档的实时显示,用来查看发送接收指令
  • 如何简单获取三个月免费试用的SSL证书
  • AI对前端开发的冲击
  • 第十课:项目部署与运维:从开发到生产
  • 仅仅使用pytorch来手撕transformer架构(1):位置编码的类的实现和向前传播