竹園論壇

標題: 102 - Ecological Bin Packing [打印本頁]

---

作者: Sylveon    時間: 2014-4-18 22:02
標題: 102 - Ecological Bin Packing
原題：http://luckycat.kshs.kh.edu.tw/homework/q102.htm
ACCODE : http://ideone.com/IVglPQ (BY Sylveon)

這題老實說…

我在挖出滿佈蜘蛛網的CODE後已經認不得它了|||

大致的想法就是DFS吧

因為是字母順序，就按字母順序遞迴吧

遞迴存到最後也可以用字串輸出

感覺上即使用DFS還是會有點小暴力

可以先把第一組（BCG）的搬移數存起來

比對搬移數，比較少時用新的疊掉

應該還不太難，好久前寫的了，這次看是重新思考

太久了，認不得它了，反正也不是個太好的方法

很久前寫的CODE現在都會看不下去

---

作者: amoshuangyc    時間: 2014-4-19 20:10


今天面試完心情不錯，看到這題心血來潮就寫了一下，嗯嗯，總是在畢業前對資訊社有了一點貢獻。
順便試一下這裡的發文系統~~

這題我是直接把所有可能都跑一遍，反正也才 6 個可能：

"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"。

以 Sample Input: 5 10 5 20 10 5 10 20 10 為例，

編號	Brown(B)	Green(G)	Clear(C)
1	5	10	5
2	20	10	5
3	10	20	10

我們嘗試計算組合 BGC 所需移動的步數：

第一個桶子最終為 B，第二個為 G，第三個為 C，

那我們需要做的是

• 將第二個桶子的 B 和第三個桶子的 B 都移到第一個桶子。
• 將第一個桶子的 G 和第三個桶子的 G 都移到第二個桶子。
• 將第一個桶子的 C 和第二個桶子的 C 都移到第三個桶子。
  

於是所需移動的步數為表格中的 (B2 + B3) + (G1 + G3) + (C1 + C2) = 75。

當我們把各個組合都計算過後，我們就可以知道哪一個組合所需移動的步數最小。這題答案是 CBG 50。

※ 桶子的 index 轉為從 0 開始數


#include <iostream>
using namespace std;

int calculate_steps(const int data[][3], const string combination) {
    int steps = 0;
   
    for (int i=0; i<3; i++) {
        if (combination == 'B')
            steps = steps + (data[(i+1)%3][0] + data[(i+2)%3][0]);
        else if (combination == 'G')
            steps = steps + (data[(i+1)%3][1] + data[(i+2)%3][1]);
        else    // combination = 'C'
            steps = steps + (data[(i+1)%3][2] + data[(i+2)%3][2]);
    }
   
    return steps;
}

int main() {
    const string combinations[6] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};
    int data[3][3];    // [[B0, G0, C0], [B1, G1, C1], [B2, G2, C2]]
   
    while (cin >> data[0][0] >> data[0][1] >> data[0][2]
                >> data[1][0] >> data[1][1] >> data[1][2]
                >> data[2][0] >> data[2][1] >> data[2][2]) {
        
        int min_steps = calculate_steps(data, combinations[0]);
        int min_idx = 0;
        for (int i=1; i<6; i++)  {
            int steps = calculate_steps(data, combinations);
            if (steps < min_steps) {
                min_steps = steps;
                min_idx = i;
            }
        }
        
        cout << combinations[min_idx] << " " << min_steps << endl;
        
    }
   
    return 0;
}

---

歡迎光臨 竹園論壇 (http://forum.tfcis.org/)

Powered by Discuz! X3.2