下料问题

Question

有谁知道如何使用背包算法来实现这个问题的算法？

我目前使用的方法广泛使用了 LINQ 和 Collections of Collections 以及一些字典。对于那些不知道我在说什么的人，请查看切削库存问题。

Answer 1

下面的代码将为您提供所有图案或剪裁组合以及允许的浪费。现在决定哪种模式将为您提供优化解决方案。仍在研究并试图弄清楚如何编写该算法。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Bar_Cutting_Recursive
{
    public class BarCuts
    {
        public int[] Qty { get; set; }
        public double TotalLength { get; set; }
        public double Waste { get; set; }
       
        public String result()  // return output.
        {
            return $"{string.Join(", ", Qty)}, TL = {TotalLength}, Waste = {Waste:F2}";
        }
    }

    internal class Program
    {
        private static double[] BarCuts = {9,8,7,6};  // List of Bar Cuttings.
        private static int BarLength = 20;
        private static double WasteRqd = 4;
        private static List<BarCuts> CutCombs= new List<BarCuts>();
        static void Main(string[] args)
        {
            int[] limits = GetLimits(BarCuts);           
            AddToCollectionRecursive(limits);
            CutCombs.Sort(delegate(BarCuts w1, BarCuts w2) { return w1.Waste.CompareTo(w2.Waste); });

            foreach (var item in CutCombs)
                Console.WriteLine(item.result());
            Console.ReadLine();
        }

        static void AddToCollectionRecursive(params int[] limits)
        {
            AddTo(new List<int>(), limits, limits.Length - 1);
        }

        static void AddTo(IEnumerable<int> value, IEnumerable<int> counts, int left)
        {
            for (var i = 0; i < counts.First(); i++)    // should change the upper limit or some break in outermost level if total > 20.
            {
                var list = value.ToList();
                list.Add(i);
                if (left == 0)
                {
                    // nt added
                    double tl = Combination_Length(list);
                    if (tl > BarLength) { break; }

                    double waste = BarLength - tl;          // BarLength = avlb bar length.
                    if (waste <= WasteRqd)
                    {
                        CutCombs.Add(new BarCuts { Qty = list.ToArray(), TotalLength = tl, Waste = waste });
                    }

                }
                else
                {
                    AddTo(list, counts.Skip(1), left - 1);
                }
            }
        }

        static double Combination_Length(List<int> CutsQty)
        {
            double tl = 0;
            for (int j = 0; j < CutsQty.Count; j++)
                tl += CutsQty[j] * BarCuts[j];
            return tl;
        }

        static int[] GetLimits(double[] Cuts)
        {
            int[] L = new int[Cuts.Length];
            for (int i = 0;i < Cuts.Length;i++)
            {
                L[i] = Convert.ToInt32(BarLength / Cuts[i]) + 1;
            }
            return L;
        }
    }
}

Answer 2

正如您给定的链接中提到的，这个问题实际上是 ILP 的一个实例，这通常是 NP 困难的。

直接来自维基百科：求解整数线性规划的高级算法包括：

• 切割平面法
• < a href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow noreferrer">分支定界
• 分支和剪切