-2

私はこのビンパッキングコードを持っています:

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

これが最善の解決策です。

何か案は？

4

1 に答える 1

0

少数のアイテムで、あらゆる可能性を試すことができます。次に、動的計画法を試すことができます。

于 2013-03-26T12:15:36.770 に答える