装箱优化最适合

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) 

的问题是：

如何做栏中的最佳optmization？

最佳专色是直到最大尺寸的元素总和，其余的较少。

在上述情况下很容易。

但是，如果我有：

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

随着少量的项目，你可以尝试所有的可能性。然后你可以尝试一个动态编程。