CODEWITHSUNDEEP
c#algorithmknapsack-problem
Sam
Sam

Reputation: 143

Cutting Stock Problem

Does anyone know how to implement the algorithm for this problem using the Knapsack algorithm?

The method I'm using at present makes extensive use of LINQ and Collections of Collections and a few Dictionaries. For those who dont know what I'm talking about check out The Cutting Stock Problem.

Upvotes: 4

Views: 3896

Answers (2)

Noel
Noel

Reputation: 39

Below code will give you all the patterns or cut combinations with your allowed waste. Now decide which of this pattern will give you the optimize solution. still researching and trying to figure out how to code that algorithm.

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;
        }
    }
}

Upvotes: 0

phimuemue
phimuemue

Reputation: 36031

As mentioned in your given link, this problem is in fact an instance of an ILP, which is NP-hard normally.

Directly from wikipedia: Advanced algorithms for solving integer linear programs include:

Upvotes: 3

Related Questions