Оптимизация упаковки бин

Question

У меня есть этот код упаковки бин:

Public Class Cortar
    Private _Cortes() As Integer
    Public BarrasCortes()() As Integer
    Private _TamanhoBarra As Integer = 100

    Public Property TamanhoBarra() As Integer
        Get
            Return _TamanhoBarra
        End Get
        Set(ByVal Value As Integer)
            _TamanhoBarra = Value
        End Set
    End Property

    Public Property Cortes() As Integer()
        Get
            Return _Cortes
        End Get
        Set(ByVal Value As Integer())
            _Cortes = Value
        End Set
    End Property

    Public Sub MelhorCorte()
        'Checks to make sure everything is initialized
        If Cortes Is Nothing Then Exit Sub

        Dim CortesCopy(Cortes.GetUpperBound(0)) As Integer
        ReDim BarrasCortes(0)
        'Bin Number we are on, Bin Element we are on, Amount placed in the current Bin
        Dim BinNumber, BinElement, BinCount As Integer
        Dim BestBin, BestBinAmount As Integer
        Dim i, j, k As Integer

        'Make a copy of the array incase we need to sort it
        DeepCopyArray(Cortes, CortesCopy)

        'Declare the first element in the first Bin
        ReDim BarrasCortes(0)(0)

        'Loop through each Element and place in a Bin
        For i = 0 To CortesCopy.GetUpperBound(0)
            BestBin = -1
            BestBinAmount = -1

            For j = 0 To BinNumber
                BinElement = BarrasCortes(j).GetUpperBound(0)

                'Count the amount placed in this Bin
                BinCount = 0
                For k = 0 To BinElement
                    BinCount += BarrasCortes(j)(k)
                Next

                'Find the most full Bin that can hold this Element
                If BestBinAmount < BinCount AndAlso BinCount + CortesCopy(i) <= Me.TamanhoBarra Then
                    BestBinAmount = BinCount
                    BestBin = j
                End If
            Next


            If BestBin = -1 Then
                'There wasn't room for the Element in any existing Bin
                'Create a new Bin
                ReDim Preserve BarrasCortes(BinNumber + 1)
                BinNumber += 1

                'Initialize first element of new bin
                ReDim BarrasCortes(BinNumber)(1)
                BinElement = 0

                BarrasCortes(BinNumber)(BinElement) = CortesCopy(i)
            Else
                'There's room for this Element in an existing Bin
                'Place Element in "Best Bin"
                BinElement = BarrasCortes(BestBin).GetUpperBound(0)
                ReDim Preserve BarrasCortes(BestBin)(BinElement + 1)
                BarrasCortes(BestBin)(BinElement) = CortesCopy(i)
            End If
        Next

        'All Cortes have been place, now we go back and remove unused Cortes
        For i = 0 To BinNumber
            For j = 0 To BarrasCortes(i).GetUpperBound(0)
                If BarrasCortes(i)(j) = 0 Then
                    ReDim Preserve BarrasCortes(i)(j - 1)
                End If
            Next
        Next

        GC.Collect()
    End Sub

    Private Sub DeepCopyArray(ByVal ArrayStart() As Integer, ByVal ArrayEnd() As Integer)
        Dim i As Integer

        For i = 0 To ArrayStart.GetUpperBound(0)
            ArrayEnd(i) = ArrayStart(i)
        Next
    End Sub
End Class

Это работает нормально, но есть проблема:

Если я определю, в C#:

var obj= new Cortar();
obj.TamanhoBarra = 100;
obj.Cortes = new int[] {48, 48, 26, 26};
obj.MelhorCorte();
int[][] x = obj.BarrasCortes;

Результат:

x[0] = {48,48} //rest 4 to 100 (TamanhoBarra)
x[1] = {26,26} //rest 48 to 100 (TamanhoBarra)

Но если я просто изменить порядок элементов в массиве на

obj.Cortes = new int[] {48, 26, 48, 26};

Результатом будет:

x[0] = {48,26,26} //rest 0 to 100 (TamanhoBarra) = best optimization
x[1] = {48} //rest 52 to 100 (TamanhoBarra)

Проблема в:

Как сделать лучшую оптимизацию для бара?

Наилучшая оптимизация - это сумма элементов до максимального размера с меньшим количеством остальных.

В вышеуказанной ситуации все просто.

Но если у меня есть:

obj.Cortes = new int[] {48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26 };

Результатом будет:

x[0] = {48,48} //rest 4
x[1] = {48,48} //rest 4
x[2] = {48,48} //rest 4
x[3] = {48,48} //rest 4
x[4] = {48,48} //rest 4
x[5] = {26,26,26} //rest 22
x[6] = {26,26,26} //rest 22
x[7] = {26,26,26} //rest 22
x[8] = {26} //rest 74

Много бара и полная потеря

Но если я расположу массив следующим образом:

obj.Cortes = new int[] {48, 26, 26, 48, 26, 26, 48, 26, 26, 48, 26, 26, 48, 26, 26, 48, 48, 48, 48, 48 };

Результат:

x[0] = {48,26,26} //rest 0
x[1] = {48,26,26} //rest 0
x[2] = {48,26,26} //rest 0
x[3] = {48,26,26} //rest 0
x[4] = {48,26,26} //rest 0
x[5] = {48,48} //rest 4
x[6] = {48,48} //rest 4
x[7] = {48} //rest 52

Это лучшее решение!

Есть идеи?

Answer 1

С небольшим количеством предметов вы можете попробовать все возможности. Тогда вы можете попробовать динамическое программирование.