1、工件的安裝與排序問題王曉楠，崔超，陳濤（中國礦業大學，徐州 221008）摘要：本文首先深入分析了組合優化的特點，然后針對本題中設備對工件排血安裝時的重量約束和體積約束的特點，就題目中提出幾個問題分別設計了不同的算法，通過不同的算法的優劣的比較，不僅較好的解決了工件的排序安裝問題，還得出了問題中算法設計的一些根據。在問題1中，我們引入了貪心策略和自適應方法對搜索算法進行改進，大大減小了搜索的規模得到了一種效率和性能都不錯的搜索算法，另外還針對數據的特點給出了一種操作簡便的簡化算法，通過兩種算法的比較得出了一些有用的算法設計結論。在問題1的算法設計過程中我們還適當的引入了一些理論證明，使算法更加

2、有說服力，最終通過MATLAB軟件得出了令人滿意的結果，有力的證明了算法的可行性。在問題2中將問題1的算法進行綜合，然后分別從不同的出發點提出了兩種算法，一種是適用性較強但不易實現的解析算法，另一種針對數據特點的較簡便的針對性算法，并比較了兩種算法各自的適應性，簡便的求出了第二組數據的排序結果，并得出第一組數據無解的結論。問題3根據前面的結論，如果只考慮重量，分析了兩種相臨扇區總重量差最大的情況，通過數學分析得出工件調整幅度，如果還要考慮體積因素，通過對工件的貪心選擇，不斷修正工件重量和體積，篩選出滿足條件的工件組合 。我們在論文的最后還給出了模型的評價和推廣。一 問題重述某設備由24個工件組

3、成，安裝時需要按工藝要求重新排序。設備的24個工件均勻分布在等分成六個扇形區域的一圓盤的邊緣上，放在每個扇形區域的4個工件總重量與相鄰區域的4個工件總重量之差不允許超過一定值（如4g）。工件的排序不僅要對重量差有一定的要求，還要滿足體積的要求，即兩相鄰工件的體積差應盡量大，使得相鄰工件體積差不小于一定值（如3）；當工件確實不滿足上述要求時，允許更換少量工件。問題1按重量排序算法；問題2按重量和體積排序算法；問題3當工件不滿足要求時，指出所更換工件及新工件的重量和體積值范圍，并輸出排序結果。請按下面兩組工件數據（重量單位：g ，體積單位：），進行實時計算：序號重量體積序號重量體積1348101.

4、51358.510323521022357.5103334710533551034349105.54351103.55347.51065355.510363471046357102733094734196832998834296.59329100.5934095.510327.598.51034497113299811342.595.112331.59912343.596.513348.5104.513357.5102.5143471051435510315346.5107.515353.5103.516348104.516356.5103.517347.510417356103.518348

5、104.518352.5104193339719342.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.52434597二 問題分析本題要求給出一種算法對24個工件按重量和體積的約束條件進行組合和排序， 并安裝到設備圓周的六個等分扇區上，每個扇區放置四個工件。相鄰扇區的工件的重量之差不允許超過一定值，而相鄰工件之間的體積差也要滿足不小于一定值的約束。表面上看似乎算法只要算法能給出一組排序滿足要求即可，不需要進行最優化，但是通過深入分析可知，由于數據可能并不理想，滿足要求的可行解的集

6、合可能很大，但也可能很小甚至并不存在，因此要提高算法的適應性就必須對排序的結果進行目標優化，使結果盡可能滿足要求，而不是簡單的給出一組可行解，這樣我們就可以通過最優或極優可行解來驗證是否可以找到可行方案。因此問題可變為如下的優化問題：其中為一組排序方案，為所有可能排序的集合。由于每個位置上的工件只能從給定的24個工件中選，因此這是一種典型的組合優化問題。問題1只要求考慮重量約束下的排序，是單目標組合優化問題。我們將目標函數定義為相鄰扇區重量之差的最大值，尋找使該值最小的排序方案。目前對于組合優化問題的解決方案主要有兩種策略，一是對搜索算法進行改進，以減少搜索的時間復雜度，如禁忌搜索算法；另一種

7、是利用遺傳算法、模擬退火算法等概率算法計算最優解。本問題所有可能的排序共有種，我們選擇第一種方法，引入貪心策略通過搜索近似最優解以大降低搜索的復雜度，然后在保證算法結果不會惡化的前提下逐漸簡化算法，提高算法的效率。問題2既要求滿足重量約束又要求滿足體積約束，是多目標優化問題，由于重量與體積之間相互并不一定有太大關聯，因此若數據不理想而兩者又要同時滿足可能是非常困難的。我們的解決辦法從滿足體積約束的排序方案中進行選擇，找出最滿足重量要求的可行方案，即把對體積的要求作為一項約束條件，按重量目標優化。當然也可以把重量作為約束條件，按體積目標優化，但是由于體積的優化牽扯到了NP-C問題，我們采用前一種

8、解決方案。問題3是在不滿足前兩個問題的情況下對個別工件進行調整，當工件不滿足要求時，允許更換少量的數據。根據前面解決問題的算法可以得出兩種修改策略：一是按重量排序；二是按重量和體積排序。針對問題一：根據問題一證明，使平均值是在不斷自我修整的，后面扇區的工件總重量最大可能接近前面扇區的總重量，但由于本設備的形狀是一個圓盤，第六個扇區與第一個扇區相臨，此時第六個扇區總重量和第一個扇區總質量之差是累計誤差最大的。三 模型的基本假設1. 圓盤被均勻分成六個扇形區域，每個區域是固定劃分的，工件是按照一定順序安裝到各個位置上去的。2. 問題1中各扇區內工件的可以隨便排列，只要工件相同都算是同一排列。四 符

9、號說明： 扇區的工件總重量： 扇區的工件平均重量： 所有工件的平均重量： 扇區和扇區的工件總重量之差，其中扇區和扇區相鄰： 相鄰區域工件總重量之差允許的最大值： 位置處的工件體積： 位置與位置處的體積之差，位置與位置相鄰： 相鄰位置處的工件體積之差所允許的最小值： 工件的全排序集： 一組排序方案： 工件總集： 算法第步操作后的剩余可選工件集：剩余可選工件集中工件的平均重量： 工件五 模型的建立和求解問題1：模型的建立：1) 理論說明：首先建立組合優化的模型，前面的分析中已經說明，我們采用的目標函數為相鄰扇區重量之差的最大值，尋找一組排序方案使這個值最小，即 （1）其中：，為第個扇區的所有可能的

10、工件組合的質量。若使用完全搜索算法，則總共需要搜索個結果，這顯然代價太高昂了，所以有必要對搜索算法進行改進。目標函數要求相鄰扇區的工件總重量之差的最大值盡可能小，由于工件擺放在設備的圓周上，易知沿某一固定方向（如順時針）相鄰扇區的工件總重量差不能一直遞增或遞減，而應保持有增有減的趨勢才可能滿足題目要求的重量約束條件，因此對這一目標進行優化得到的各扇區的工件總重量相對而言一定比較接近且一定在所有工件重量的平均值附近，針對目標函數的這一要求，我們可以對目標函數進行轉化，將目標函數轉換為： （2）通過分析可知目標函數（2）的要求比目標函數（1）的要求要強，即滿足目標函數（2）一定能滿足目標函數（1）

11、，也就是說目標函數（2）對目標函數（1）具有充分性。當然這里只是從直觀的角度去分析的，下面將給出理論上的嚴格說明。我們對24個工件進行排序，假設找到一組排序，設每個扇形區域的總重量分別為、，為了使每個扇形區域的工件總重量與相鄰區域的工件總重量之差盡可能的小，使其滿足不超過一個定值（如4），這就要求、盡量的相等，既接近算術平均值4。如果我們從24個工件中找到這組排序，使每個扇區的重量分別為、即最接近算術平均值4的一組排序，而它們當中卻有兩個相鄰扇形區域的總重量超過一定值（如4），即不滿足重量條件，則可得出：這24個工件無論怎么排序都不能滿足每個扇形區域的四個工件總重量與相鄰區域的四個工件總重量之

12、差不允許超過一定值（4）這個條件。下面來證明我們的結論：結論一：如果從24個工件中找到一種排序，使每個扇區4個工件的總重量、盡量相等，即等于所有工件重量的算術平均值4，則每個扇形區域的工件總重量與相鄰區域的工件總重量之差的和最小，同時也使相鄰兩個扇形區域的總重量之差的最大值最小，即這種排序為最優排序。證明：假設存在另外一種排序，在六個扇形區域重量的排序為、，其中 則相鄰扇形區域的重量差為：我們知道對于不等式，當時取等號，故：當時，取最小值。同理、也能取最小值。由于、離散取值，由條件可知每個扇區的總重量近似相等，即、，此時、；又由于，所以此時這樣就證明了此排序使每個扇形區域的工件總重量與相鄰區域

13、的工件總重量之差的和最小，同時也使相鄰兩個扇形區域的總重量之差的最大值最小，即這種排序為最優排序。結論二：如果找到一種排序，使每個扇形區域的四個工件的總重量盡量相等，即接近于4，而這種排序不滿足重量的約束要求，即不能使所有相鄰扇形區域的重量差小于一定的值（4），則得出結論：這24個工件無論怎么樣排序，都不能滿足重量要求。根據結論一，我們得到了這種排序即每個扇區四個工件總重量盡量等于4是最優排序，使相鄰兩個扇形區域的總重量之差的最大值最小，如果這種最優排序都不滿足要求，則其它的排序一定不滿足要求。2) 算法設計：如何找到這種排序，使每個扇形區域的四個工件總重量盡量相等，即等于4。此類問題是典型的

14、組合優化問題。為了解決這一問題，我們可以對完全搜索算法進行改進，通過在搜索算法中引入貪心策略，將較大的搜索空間分為幾個小的搜索空間，可以大大減小搜索規模而搜索的結果不會惡化，即至少仍可以得到一組近似最優解甚至是全局最優解。算法一：引入貪心策略的搜索算法算法步驟：Step1：初始化。求出24個工件的平均值，給出初始可選工件集合。Step2：從可選的工件集中選出四個工件，選取原則為工件組合的重量平均值最接近于。Step3：從初始可選工件集中去掉已選擇的4個工件，得到剩余可選工件集，之后有兩種操作方法：一種方案是用代替重復進行Step2，直至工件選完全部安裝到設備上，標準重量平均值始終用，我們稱之為

15、固定平均值法；另一方案是求出剩余可選工件集中工件的平均重量，用、代替和，重復進行Step2，直到工件選完全部安裝到設備上算法結束，標準重量平均值用剩余可選工件集的平均重量，這種稱為自適應平均值法。引入貪心策略后，搜索算法的規模為，主要由前兩項決定，同完全搜索算法的規模相比計算式中的各部分由相乘變為相加，規模大為降低，這使得計算機求解變得不僅可行而且十分簡便快捷。至于結果是否合理我們將在模型求解中討論。這里之所以采用貪心策略，是考慮到由于工件數較多，工件可能的組合數會更多，我們將第1步操作之前和第2步操作之前的所有可選工件組合的重量平均值制成下面的兩幅圖，以便于同所有工件重量平均值進行直觀的比較

16、：圖1.算法第1步選擇扇區1的工件組合圖2.算法第2步選擇扇區1的工件組合由圖可知有相當一部分工件組合的平均重量在平均值附近，這樣第步操作選出的工件組合的重量均值就可以非常接近于剩余可選工件集中工件的重量平均值，因此將它們選出后對剩余的工件集合的重量平均值產生的影響就是微乎其微的，這樣步操作的候選組合中仍然可以找到盡可能接近于總體平均值的組合，因此算法就很有可能是可行的。我們知道只有具有“貪心選擇性質”的問題用貪心算法才能求得全局最優解，否則只能得到局部最優解3。下面我們對問題的貪心選擇性質和局部最優進行說明。i. 貪心選擇性質：根據前面的證明，我們可以得到結論：如果使圓盤上的工件組合滿足重量

17、條件，應該使得各個扇形區域上的工件重量之和盡可能相等，這樣如果從扇區一開始，那么為當前最接近4的，即可以滿足在第一個扇區，是可能的最優解。ii. 局部最優解：如果前面的k-1個扇形區域上的工件已經尋找出來，那么第k個扇形區域上的工件重量只要滿足和第k-1個的重量差最小。因為：在這里，只是把該問題化成一個子問題，在該問題里面，也是尋求最優組合，使之滿足相鄰的扇區工件重量差最小的條件。這樣，就把k之后圓盤的各個扇區化成一個類似與原來24個工件排列的問題。這樣，該問題滿足局部最優解。算法二：算法一的簡化算法主要思想如下：通過對題目給出的數據進行分析，可得如下兩幅圖：圖3.第一組數據的重量和體積分布圖

18、4.第二組數據的重量和體積分布通過對兩幅圖片的分析可知，兩組數據中工件按重量和體積明顯分等為兩類，這很可能跟設備的實際工作情況有關，也就是說此設備的工作環境中工件的重量和體積是有一定要求的，因此我們可以根據具體的數據和實際情況來設計出一種針對性的算法，根據具體的數據可以將算法大大簡化。由于工件按重量明顯分為兩組，且同組工件之間重量接近，因此要使每個扇區的平均重量最接近總平均重量必須兩組各取兩個，否則就會因搭配問題使大大偏離，從而難以完成目標的優化，根據這一思路，我們可以得到如下過程的算法：首先將所有工件的重量按大小排序；選出重量最大的和最小的工件，按一定的旋轉方向放在一個扇區中的兩個相鄰的位置

19、上；選出剩余工件中重量最大和最小的工件，按相同的旋轉方向放在接下來的位置上；重復操作，直到所有的工件被選完，算法結束。3) 模型求解： 根據題目所給數據和我們給出的算法，我們通過MATLAB軟件編程得到各組數據的排序結果：表一：用固定平均值法求得第一組數據的排序結果區域扇形區域1扇形區域2扇形區域3工件位置123456789101112工件序號13724251020481217每個區域的重量/135713571357區域扇形區域4扇形區域5扇形區域6工件位置131415161718192021222324工件序號6913211114161915182223每個區域的重量/p>

20、7.5最大重量差：0.5表二：用自適應法求得第一組數據的排序結果區域扇形區域1扇形區域2扇形區域3工件位置123456789101112工件序號13724251020481217每個區域的重量/135713571357區域扇形區域4扇形區域5扇形區域6工件位置131415161718192021222324工件序號6913211114161915182223每個區域的重量/135713571357.5 最大重量差：0.5由上面的結果可見，引入貪心策略后，搜索的結果仍然很好，最大的重量差為0.5，而且用固定平均值法與用自適應平均值法所得結果相同。在本題中，0.5是最小重量差，而第一組數據中所有工

21、件重量的平均值為339.271，任何一個扇區內工件組合的平均值都不等于這個值，所以最終的全局最優排序一定不可能滿足各扇區工件總重量都相等，所以這里求得的就是全局最優解，可見算法一具有優良的性能。表三：用固定平均值法求得第二組數據：區域扇形區域1扇形區域2扇形區域3工件位置123456789101112工件序號1292135710461124每個區域的重量/1395.51395.51395.5區域扇形區域4扇形區域5扇形區域6工件位置131415161718192021222324工件序號81213181416192215172023每個區域的重量/1395.51395.51394.5最大重量差

22、：1.0表四：用自適應法求得第二組數據的排序結果：區域扇形區域1扇形區域2扇形區域3工件位置123456789101112工件序號129213571046824每個區域的重量/1395.51395.51395區域扇形區域4扇形區域5扇形區域6工件位置131415161718192021222324工件序號111215171314222316181920每個區域的重量/1395.513951395.5最大重量差：0.5對比第二組數據的這兩組結果可以發現自適應平均值法與固定平均值法略有不同，且自適應平均值法的排序結果優于固定平均值法。這不難理解，因為固定平均值法一直使用原來的所有工件重量平均值，而

23、扇區內的工件組合重量平均值不可能精確等于所有工件重量平均值，這樣之前的操作中所產生的誤差會在后來的操作中積累下來，所以固定平均值法的排序結果中重量差最大值總是出現在最后一項。而對于自適應平均值法，由于每次操作時所使用的平均值總是當前剩余可選工件集的重量平均值，它能實時反映系統當前的狀態，并能及時作出調整，避免了重量差的積累，因此效果由于固定平均值法。表五：用算法二求得的第一組數據的排序結果：區域扇形區域1扇形區域2扇形區域3工件位置123456789101112工件序號210481391111671820每個區域的重量/1357.51354.51356區域扇形區域4扇形區域5扇形區域6工件位置

24、131415161718192021222324工件序號512172232362414211519每個區域的重量/13581357.51359最大重量差：3表六：用算法二求得的第二組數據的排序結果區域扇形區域1扇形區域2扇形區域3工件位置123456789101112工件序號121291376231622178每個區域的重量/1395.51396.51396區域扇形區域4扇形區域5扇形區域6工件位置131415161718192021222324工件序號511319141215101820424每個區域的重量/1395.513961392.5最大重量差：3.5 可見，算法二的結果也是滿足要求的

25、，但這種簡化算法的性能不如算法一，因為它并沒有確切的目標數來約束它，它只是針對具體的數據而設計的，因而算法比較簡單且易操作，但它的缺點就是只適應于某一類特點的數據，不易推廣。問題2：模型的建立：算法一：綜合法本問題要求給出一個同時滿足重量和體積約束條件的算法，但是由于在本題中重量與體積之間并沒有直接的聯系，因此難以找到一種統一的進行優化的規則，若分別進行優化則一方面會導致算法的復雜度過大（對兩個大的解空間進行搜索），另一方面遵循重量約束的組合目標優化的可行解與遵循體積約束的組合目標優化的可行解之間并不一定相容，也就是說兩個解集不一定有交集。即使有交集，要實現這一運算也是要花費高昂的代價的。不過

26、在優化求解之前，我們仍然可以通過兩個約束條件的單獨組合優化來驗證僅考慮一個約束條件時的可行解是否存在從而可能簡化處理過程。這樣我們得到算法一的過程如下：過程一（可行性驗證）：驗證單一約束條件下可行解是否存在，即滿足重量之差不大于給定值的可行解是否存在，滿足體積之差不小于給定值的可行解是否存在。若找不到滿足約束條件的可行解，則算法結束，返回不能滿足要求的信息。過程二（可行解尋找）：將對體積的約束條件嵌入到問題1的算法一中去，作為搜索過程中的一項約束條件，即在搜索過程中工件組合必須滿足體積的要求，若進入了不滿足體積要求的空間則退到上一層循環中去以退出不滿足要求的空間。在過程一中，由于不僅要對重量約

27、束進行可行性驗證，還要對體積約束進行可行性驗證。而問題1中只給出了重量排序算法，沒有給出體積排序算法，因此在這里有必要給出滿足體積約束條件的排序的簡單說明。體積約束下的工件排序：由于體積條件為相鄰位置之差不小于給定值，這一點不同于問題一的重量排序算法，因此不能再像問題1中的進行目標轉化并引入貪心策略，但是體積條件是相鄰工件之間的約束，根據這一點我們可以構造一個體積差矩陣，矩陣中的每個元素。根據題目所給的最小體積差，我們可以將體積差矩陣轉化為一個0-1矩陣，轉換規則為：若，則，表示工件與可以放在相鄰的位置上；否則，表示工件與不能放在相鄰的位置上。我們的目標就是尋找一組可行的排列是體積要求得到滿足

28、。不難發現若把作為一個鄰接矩陣，則可以表示成一個無向圖，圖的每個頂點表示一個工件，兩頂點之間有邊則說明這兩個頂點表示的工件可以放在相鄰的位置上，無邊則表示兩個工件不能放在相鄰的位置上。這樣進行體積排序實質上就轉化為尋找這個圖中的哈密頓回路問題。由于科學早已有了結論，即判定任意一個圖是否是哈密頓圖的問題是一類NP-完全問題，更何況要在較短時間內輸出所有的哈密頓回路,所以這一問題的解決是相當困難的。盡管已經存在一些尋求一個圖的哈密頓回路的方法，如分支算法和約束算法等。但所有這些算法都不是很有效的，其時間復雜度幾乎是不可接受的。因此我們只能通過圖論中的一些必要條件證明某個圖不是哈密頓圖，以省掉后面不

29、必要的分析。算法二：針對性算法算法一雖然是希望盡量通過解析的方法來達到組合優化的目的，但是無疑算法實現的難度太大了，且算法的效率也不是很好。因此有必要從具體的數據入手來尋找更有效、更易于實現的算法。仔細分析數據不難發現兩組數據有一些共同點，但也有一些區別，數據中有著比較大的規律。因此最好的辦法應該是從具體的數據入手，分析數據的特點，然后設計算法進行優化排序，兩組數據的共同之處就是工件無論是按重量還是按體積都可以明顯的劃分為兩組，一類是大重量、大體積，另一類是小重量、小體積（當然這里的大小只是相對而言，并不是說兩組工件的重量和體積真的相差很大）。而不同之處在于：第一組數據兩組之間體積差別并不明顯

30、，這一點不利于體積的優化排序，但重量差別明顯，且同組工件重量差不大，分布均勻；第二組數據則相反，兩組工件之間體積差別明顯，且同組的工件體積差不大，但同組工件的重量不如第一組數據分布的那么集中，但問題1的算法同樣適用。針對兩組數據各自的特點，我們應該采取不同的處理過程。對第一組數據，由于重量分布集中且組間差別明顯而體積差別不明顯，且組內工件體積之差就可以達到本題的要求，所以對體積約束條件來說，顯然組間工件的約束相對要強一點，而組內工件的約束相對于第二組數據要弱一點，總的來說兩組工件的體積分布更接近一些，因此仍然需要使用算法一，先進行體積排序可行性的驗證。若驗證體積排序可行，再根據各組組內工件重量

31、分布比較接近（重量至多差5.5），組間工件的重量差較大（至少為15）的特點，要滿足重量的約束條件，則必須保證個扇區內的工件組合為“兩大兩小”的形式，即兩個大重量工件加兩個小重量工件，這樣才可能滿足重量約束條件，據此約束條件得以轉化為較簡單的形式。在此前提下，再次利用貪心策略，選擇與當前工件滿足體積差要求但體積差最小的工件安裝在當前工件旁邊。第二組數據的算法的描述如下：Step1：體積約束排序可行性驗證。Step2：根據貪心策略進行搜索，選擇當前工件滿足體積差要求但體積差最小的工件。Step3：驗證是否滿足重量約束條件，即一個扇區內“兩大兩小”的形式，若不滿足，將此工件排除在外，重復Step2；

32、若滿足，將選出的工件按裝在當前工件的旁邊位置，并作為新的當前工件，重復Step2。當工件安裝完畢后算法結束。而對于第二組數據，體積分布較為集中，組間體積差較大，由圖4可知，體積接近的工件組內工件體積差不超過3，因此可以證明排序時必須兩組工件交替安裝，即當前位置安裝了一個大體積的工件時，下一個則必然是小體積的工件。而由問題1算法一可知，通過貪心策略得到的非常接近于平均值的工件組合一定是2個大重量工件加2個小重量的工件，根據圖4的對應關系，也就是2個大體積的工件加2個小體積的工件，這樣就可以直接利用問題1的結果，在一個扇區排序使大小工件交錯安裝，同時保證扇區交界處的工件也滿足這一要求即可。因此針對

33、這一類數據就可以直接利用問題1的結果的進行重排序。第二組數據的排序算法如下：Step1：利用問題1的算法一選出滿足重量約束條件的工件組合。Step2：第一步的結果進行重排序，原則是：組合關系不能改變，大小體積的工件交替安裝在設備的圓周上。易知，排序組合可以有很多，而我們只要給出滿足要求的一組就可以。顯然這種方法只適合于兩組工件重量差別較大的情況，若重量相差不多，則Step1得到的結果可能不是“兩大兩小”的組合，此時這一算法就不再適用了。這時應該增加約束條件，使Step1結果滿足“兩大兩小”的組合方式，才能繼續使用，這樣實際上又回到了算法一，只是由于工件體積分布的規律性不需要體積約束的驗證了。模

34、型的求解：先求第二組數據的排序結果。根據問題1的自適應平均值排序算法的結果，利用算法二得到如下排序結果：區域扇形區域1扇形區域2扇形區域3位置123456789101112序號192213751048624體積/10395.5103981039610397103.596.510297區域扇形區域4扇形區域5扇形區域6位置131415161718192021222324序號151117121322142316191820體積/103.595.1103.596.5102.59610396103.59810496.5可見，體積間隔和重量間隔均滿足要求。對第一組數據，我們首先進行了體積約束的驗證。首先

35、給出一個判斷哈密頓圖的充分條件：狄拉克Dirac定理1：設是含個頂點的簡單無向圖，其頂點的最小度用表示。若，則是哈密頓圖。我們用MATLAB軟件求出了各工件之間體積差的鄰接矩陣，然后得出了所有頂點的度為：故，而，所以，因而這是哈密頓圖，存在哈密頓回路，即工件滿足體積條件。第二步，利用貪心策略搜索，根據問題三，我們可以看到序號10的工件有這較大的偏差，根據貪心選擇性質，對十號重量修改為332，這樣同時滿足以上結論。問題三：當工件不滿足要求時，允許更換少量的數據。根據前面解決問題的算法可以得出兩種修改策略：一是按重量排序；二是按重量和體積排序。針對問題一：根據問題一證明，使平均值是在不斷自我修整的，后面扇區的工件總重量最大可能接近前面扇區的總重量，但由于本設備的形狀是一個圓盤，第六個扇區與第一個扇區相臨，此時第六個扇區總重量和第一個扇區總質量之差是累計誤差最大的。因此，如果存在不滿足的工件，最有可能在第六個扇區選擇工件是出現，這樣根據算法可以選擇出來最有四個工件，可以對該四個工件中某個工件做適當的調整，以達到滿足條件的工件出現。