瑞の資訊備忘錄

一、目的：在固定的限制中進行裝箱或是依照重量放置物體到不同的箱子是歷史上有趣的問題，某些

            裝箱問題是NP-complete，但是可以使用動態規劃法 (Dynamic Programming)或是

            啟法式演算法(Heuristic)來解決這類型的問題。     (連結UVa online原文題庫)

二、問題說明：

     回收玻璃的問題主要是將回收的玻璃分成棕色(Brown)、綠色(Green)、透明(Clear)三種不同顏色

     的種類後將不同堆但是同顏色的玻璃瓶移至同一堆，但是處理過程中必須儘量減少玻璃瓶的移動數量。

     該問題在兩個條件下成立：

         (1) 可在同一堆中放置無限數量的玻璃瓶            (2)所有的玻璃瓶的數量小於2^31

三、輸出與輸入的規則：

      每次輸入一組9個整數的數值，代表三種不同顏色的玻璃瓶各三堆及數值則表示每堆的玻璃瓶的數量；數值得順序

      所表示的產色依序是: 棕色(Brown) 綠色(Green) 透明(Clear) 棕色(Brown) …… 透明(Clear)。輸出解答時必

      須在同一行中輸出各顏色(B,C,G)玻璃移動後的順序和總移動瓶子的數量。

      PS: 1. 輸入時一組內的整數空白間隔可能超過一個。

             2.當答案不止一個時必須依字母的順序由小到大輸出。

    EX: Sample Input                                Sample Output

            1 2 3 4 5 6 7 8 9                =>        BCG 30

            5 10 5 20 10 5 10 20 10      =>        CBG 50

四、演算法說明：

這個問題沒有太多複雜的技巧，只是單純進化版的排列組合的問題：

     4-1、 由於調整輸入資料的順序使其符合題目的需求來減少後續程式的判斷。

     4-2、 透過計算每個顏色在不位置上所須的搬移量來建立一個Weight Matrix。

     4-2、 使用遞迴式和Wight Matrix來求出所有排列組合中最少搬移量的組合。

Run time of UVa online web : 0.036 sec

Download : UVa102_EcologicalBinPacking.tar.gz

Result：