高分求一装箱算法，来着有分~~~

Question

有若干种规格的箱子，可装小球的数量不同
现有小球若干，如何装箱可以满足以下两个条件：
1.箱数最少
2.箱子最满举个例子：
4个箱子，分别能装小球200，150，100，80个
求440小球如何装箱？
答案是1，2，3号箱各一个

Answer 1

装箱问题近似算法的并行化
张 蕾  SA02011130
摘要：装箱问题（bin packing problem）是一个著名的NP难解问题，其在工业生产及日常生活中有广泛的用途，所以具有重要的研究价值。本文首先对装箱问题进行了简要的介绍，然后介绍了两种一维装箱问题的近似算法并讨论了其相应的并行化算法，即下次适应算法及其并行化算法和调和装箱算法极其并行化算法。
关键词：装箱问题   并行算法  近似算法1．引言
装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以装箱问题有着广泛的应用背景，具有很大的研究价值。
装箱问题是经典的NP难解问题，这意味着该问题不存在在多项式时间内求得精确解的算法（如果P≠NP）因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。目前，已经提出了大量的近似算法，如下次适应（Next Fit）、首次适应（First Fit）、最佳适应（Best Fit）、调和（Harmonic-K）算法等。这些串行算法已经具有了比较好的性能，表1给出了这些研究成果的三种重要性能指标，装箱问题近似算法的三个评价标准是最坏情况性能比，平均情况性能比（如非特别指出，一般是指当输入物品满足(0,1]均匀分布情况下的平均性能），时间、空间复杂度。Coffman等从这三个主要标准出发对众多目前已经提出的算法进行了很好的评价[2]，下面列出其中一部分。
表1 一些著名的经典装箱问题近似算法
近似算法 脱/在线 时间复杂度 最坏情况性能比 平均性能比
下次适应算法(NF) 在线 O(n) 2 4/3
首次适应算法(FF) 在线 O(nlogn) 1.7 1
最佳适应算法(BF) 在线 O(nlogn) 1.7 1
调和算法(HK) 在线 O(n) 1.69103… 与K相关
改进的调和算法(RH) 在线 O(n) ≤1.63596… 与K相关
Next Fit-K(NFK) 在线 O(n) 1.7+0.3/(K-1) 与K相关
AFBK 在线 O(n) 1.7+0.3/(K-1) 与K相关
K-Bounded Best Fit(BBFK) 在线 O(n) 1.7 与K相关
ABFK 在线 O(n) 1.7+0.3/K 与K相关
降序首次适应算法(FFD) 离线 O(nlogn) 11/9 1
降序最佳适应算法(BFD) 离线 O(nlogn) 11/9 1装箱问题中最早被研究的是一维装箱问题。随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题所与生俱来的复杂性，虽然已经有一些研究成果发表了，但是其研究还是相当的困难。本文所讨论的还是一维装箱问题。2．部分相关知识
在研究装箱问题的并行化之前，我们先来了解一下一些相关的知识。
2．1 在线算法、离线算法与半在线算法
在线算法：如果一个近似装箱算法在执行过程中，每当一个物品到达时，就立刻决定把该物品放入哪个箱子中，而不管后序物品如何，这种算法就被称为在线算法。下次适应算法、首次适应算法、K-调和算法等等都是在线算法，其时间复杂度都为O(n)，但下次适应算法的最坏情况性能比较高（为2），而K-调和算法对此有较大改善（为1.6910)。
  离线算法：如果算法在开始装箱之前，已经预先得到了所有物品的信息而一次性的确定装箱策略，这种算法就被称为离线算法。降序首次适应算法和降序最佳适应算法是两个重要的离线算法，它们首先对所有物品按照物品大小的降序排序，然后对这个排序后的物品序列分别应用在线算法中的首次适应、最佳适应策略。由于离线算法预先知道所有物品的信息，因此算法的性能一定远远优于在线算法。
半在线算法：与在线算法相同它不要求预先知道所有的物品信息，物品一到达，立刻决定把该物品放入哪个箱子中，与在线算法的区别在于它每次处理当前物品的时候允许对前面已经完成装箱的物品做有限的调整（比如常数个物品的调准）。
2．2 适应算法
    适应算法(Any Fit Algorithm)：当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子，符合该条件的算法被称为适应算法。下次适应算法、首次适应算法、最佳适应算法、最坏适应算法和几乎最坏适应算法是几个著名的适应算法。适应算法的最坏情况性能比被证明一定处于[1.7,2]范围内，即在最坏情况性能上不可能优于首次适应算法。

Answer 2

不行,内容太多.想把一篇论文给你看看.留个email

Answer 3

'=================================================
'CBoxs.cls
'=================================================
Private m_Boxes() As CBox
Public Property Let NewBox(value As CBox)
    ReDim Preserve m_Boxes(UBound(m_Boxes) + 1) As CBox
    Set m_Boxes(UBound(m_Boxes)) = value
End PropertyPublic Property Get LeftContains(ByVal Index As Long) As Long
    Dim i As Long
    Dim pBox As CBox
    
    For i = Index + 1 To UBound(m_Boxes)
        Set pBox = m_Boxes(i)
        LeftContains = LeftContains + pBox.nMax * pBox.nNum
    Next i
End PropertyPublic Function Div(ByVal nBall As Long) As String
    Dim i           As Long
    Dim dNum        As Double
    Dim nDivBall    As Long
    
    nDivBall = nBall
    'check if has enough space
    If LeftContains(0) < nDivBall Then
        Div = "the ball number larger than all boxes' space "
        Exit Function
    End If
    
    For i = 1 To UBound(m_Boxes)
        If m_Boxes(i).nMax * m_Boxes(i).nNum >= nDivBall Then
            
            dNum = ndivall / Format(m_Boxes(i).nMax, "#.0000")
            dNum = CLng(dNum) + IIf(CLng(dNum) - num = 0, 0, 1)
            If dNum = 0 Then dNum = 1
            
            Div = Div & "Type:" & m_Boxes(i).nMax & "----" & dNum & vbCrLf
            Exit Function
            
        Else
            Div = Div & "Type:" & m_Boxes(i).nMax & "----" & m_Boxes(i).nNum & vbCrLf
            nDivBall = nDivBall - m_Boxes(i).nMax * m_Boxes(i).nNum
        End If
    Next i
    
End FunctionPrivate Sub Class_Initialize()
    ReDim m_Boxes(0) As CBox
End Sub

Answer 4

'========================================
'CBox.cls
'========================================
Public nMax As Long ' max contain number
Public nNum As Long 'number of these boxes

Answer 5

'=======================
'Form1.frm
'========================
Private Sub Command1_Click()
    
    Dim nBall
    Dim pBox As CBox
    Dim objBoxs As New CBoxs
    
    Set pBox = New CBox
    pBox.nMax = 200
    pBox.nNum = 1
    
    objBoxs.NewBox = pBox
    
    Set pBox = New CBox
    pBox.nMax = 150
    pBox.nNum = 1
    objBoxs.NewBox = pBox
    
    Set pBox = New CBox
    pBox.nMax = 100
    pBox.nNum = 1
    objBoxs.NewBox = pBox
    
    Set pBox = New CBox
    pBox.nMax = 80
    pBox.nNum = 1
    objBoxs.NewBox = pBox
     
    nBall = 440
    
    MsgBox objBoxs.Div(nBall)
    
End Sub

Answer 6

用递归的办法遍历所有装箱可能，然后找出用箱子最少并且剩余空间最小的方案。关键看着两个条件的优先级哪个高。比如说360个球，最少箱子的方案是两个200的箱子，最少浪费空间的方案是一个200的两个80的。
我下面给出的代码是以最少箱子的优先级更高'LeftBall:剩余未装箱球的数量，第一次传入球的总数
'arybox:  传入箱子数组
'begin:   第一次传入的标志，第一次传入true
'BoxSel:  递归过程中传递的参数，不必传入
Private Function test(ByVal LeftBall As Integer, ByVal arybox As Variant, begin As Boolean, Optional ByVal BoxSel As String) As String    Static BestSel As String
    Static BestSpaceLeft As Integer
    Static BestCount As Integer
    
    Dim i As Integer
    Dim tmpLeftBall As Integer
    Dim tmpBoxSel As String
    Dim tmpCount As Integer
    
    If begin Then
        BestSel = ""
        BestSpaceLeft = 400
        BestCount = 100
    End If
    
    For i = LBound(arybox) To UBound(arybox)
        DoEvents
        tmpLeftBall = LeftBall - arybox(i)
        tmpBoxSel = BoxSel & i & " "
        If tmpLeftBall <= 0 Then
            tmpCount = Len(tmpBoxSel) / 2
            If tmpCount <= BestCount Then
                If Abs(tmpLeftBall) <= BestSpaceLeft Then
                    BestSpaceLeft = Abs(tmpLeftBall)
                    BestSel = tmpBoxSel
                    BestCount = tmpCount
                End If
            End If
            'Debug.Print tmpBoxSel
        Else
            Call test(tmpLeftBall, arybox, False, tmpBoxSel)
        End If
    Next
    test = BestSel
End Function调用举例：
Dim arybox(1 To 4) As Integerarybox(1) = 200
arybox(2) = 150
arybox(3) = 100
arybox(4) = 80Debug.Print test(440, arybox, True)
Debug.Print test(360, arybox, True)
Debug.Print test(501, arybox, True)输出：
3 2 1 
1 1 
2 1 1 440个球3号箱子用一个2号箱子用一个1号箱子用一个
360个球1号箱子用两个
501个球2号一个一号两个，剩余空间49