Skip to main content

【UVa】102 Ecological Bin Packing

英文題目傳送門，中文題目傳送門

最最開始的想法是，取每個桶子裡最多玻璃瓶的種類做為該桶要裝的顏色，But會延伸出很多很多問題，像是如果剛好有兩個桶子有相同的最多數量時，需要再計算兩個桶子分別被指定為該顏色下的移動數，然後再比較，若是三個桶子的最大數目都一樣的話就更複雜了...

在過程中發現另外一種思考方式，如果是用瓶子的總數 - 每個桶子指定顏色的瓶子數，取最小值，這樣也是最少移動次數的配置，幸好題目指有三種顏色，六種可能性還hold得住。


以下為程式碼：

#include <stdio.h>
#include <stdlib.h>

int getSumOfBottles(int bottles[3][3]){
    int i, j, sum;
    int i, j, sum = 0;
    
    for(i = 0; i < 3; i++){
         for ( j = 0; j < 3; j++){
            sum += bottles[i][j];
         }
    }
    
    return sum ;
}


void showBGC( int inputNum ){
    switch (inputNum ){
         case 0 :
            printf ("B");
             break;
         case 1 :
            printf ("G");
             break;  
         case 2 :
            printf ("C");
             break;  
    }
}

/* method 2*/
/* just use 6 kinds of posibilities to count*/

int main( int argc , char *argv []) {
    
    int i, j;
    
    /* char array, with ', B == 0, G == 1, C ==2 */
    char bcgText [3] = {'B' ,'G','C'};
    
    /* since BCG should show up in the begining, move {0, 2, 1} */
    int posibleIndex [6][3] = {{0, 2, 1}, {0, 1, 2}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2 , 1, 0}};
    int posibleIndex [6][3] = {{0, 2, 1}, {0, 1, 2}, {2, 0, 1}, {2, 1, 0}, {1, 0, 2}, {1, 2, 0}};   

    int bottles[3][3];
    
    int sumBottles;
    int sumMove;
    
    int minMove;
    int minMoveIndex = 0;
    
    while(scanf("%d%d%d%d%d%d%d%d%d" ,&bottles[0][0], &bottles[0][1], &bottles[0][2],
                                      &bottles[1][0], &bottles[1][1], &bottles[1][2],
                                      &bottles[2][0], &bottles[2][1], &bottles[2][2]) != EOF){
        
        sumBottles = getSumOfBottles(bottles);
        minMove = sumBottles;
    
         /* get the moves in each cases, and find the minMovements */
         for ( i = 0; i < 6; i++){
            sumMove = sumBottles - (bottles[0][posibleIndex[i][0]] + bottles[1][posibleIndex[i][1]] + bottles[2][posibleIndex[i][2]]);
            
             if ( sumMove < minMove){
                minMove = sumMove;
                minMoveIndex = i;
                 /* printf("index %d, minMove %d", i, minMove); */
             }
         }
    
         /* one line output */
        printf ("%c%c%c %d\n", bcgText[posibleIndex[minMoveIndex][0]],
                              bcgText[posibleIndex[minMoveIndex][1]],
                              bcgText[posibleIndex[minMoveIndex][2]], minMove);        
    }
    return 0;
}

  
但是不知道為什麼在UVa上一直得到wrong answer的回覆，搞了老半天還是不知道為什麼...

不管了，在zerojudge達成AC就好惹

不知道為什麼一直在UVa上被說是WA，決定貼上stackoverflow求助，原來是按照字母順序的部分沒有做完全=口=
之前的版本只有做1/3套，把BCG、BGC放對，接下來應該是要CBG、CGB再以此類推，當時不知道大腦被塞進哪個牆，覺得C跟G都不用排序...另外也感謝網友的指正，sum在使用時要先規0!

另外補上找資料的時候看到的厲害程式碼，使用了enum{B = 0, C = 1, G = 2};讓程式更好讀!

/**
 * UVa 102 Ecological Bin Packing (AC)
 * Author: http://chchwy.blogspot.com
 * Last Modified: 2008/09/10
 */

#include<iostream>

enum{B = 0, C = 1, G = 2};

int main()
{
    //六種排列組合
    int binColor[][3]={ {B, C, G}, {B, G, C}, {C, B, G},
                        {C, G, B}, {G, B, C}, {G, C, B}};

    char s[][4]={"BCG", "BGC", "CBG","CGB", "GBC", "GCB"};

    int bin[3][3];
    while(scanf("%d%d%d%d%d%d%d%d%d",
                &bin[0][B], &bin [0][G], &bin[0][C],
                &bin[1][B], &bin [1][G], &bin[1][C],
                &bin[2][B], &bin [2][G], &bin[2][C]) != EOF)
    {
        int currentMove =0;
        int totalGlasses =0;

        for(int i=0; i<3; i++)
            totalGlasses += (bin[i][B] + bin [i][G] + bin[i][C]);

        int minMove = totalGlasses ;
        int minNo = 0; //第 minNo號排列組合move最少

        //六種排列組合都跑過一次
        for(int i=0;i<6 ;i ++){ // 移動的次數 = 總瓶數- 不用移動的瓶數
            currentMove = totalGlasses
                - bin [0][binColor[i][0]]
                - bin [1][binColor[i][1]]
                - bin [2][binColor[i][2]];

            if(currentMove <minMove){
                minMove = currentMove ;
                minNo =i ;
            }
        }
        printf ("%s %d\n", s[minNo],minMove);
    }
    return 0;
}



這封郵件來自 Evernote。Evernote 是您專屬的工作空間，免費下載 Evernote
Labels:

Comments

Post a Comment

Popular posts from this blog

淺介I2C

I 2 C 起源 內部整合電路（ Inter-Integrated Circuit, I 2 C, 讀做 I-square-C ）是由飛利浦半導體公司開發的一種專用介面。 I 2 C 是以最少的連接線進行硬體佈線還要有靈活擴充的特性為目標而設計，最後出現了只有以序列資料線 SDA （ Serial DAta ）及序列時脈線 SCL （ Serial CLock ）來進行所有通訊的 I 2 C 介面， I 2 C 允許多主（ master ）多僕（ slave ）系統，其傳輸系統內每一個裝置都有唯一的地址可供辨識。資料的寫入和讀取都是由 master 主動發起， slave 無法主動向 master 回報，除非使用中斷腳通知 master 。 I 2 C 傳輸速度有慢（小於 100Kbps ）、快（ 400Kbps ）及高速（ 3.4Mbps ）三種，每一種均可向下相容。 I 2 C 電路配置 如前所述 I 2 C 為兩線式，一為時脈線 SCL ，另一條為資料線 SDA ，硬體線路如圖 1 ，兩線皆為雙向性，且都需要透過高接電阻（ pull-up, 對岸說的上拉電阻）接電。平常不使用時， SCL 與 SDA 的訊號都處於高電位。為了多裝置共線的功能，裝置的 SCL 和 SDA 腳位要為 開洩極（ open-drain ） 或 開集極（ open-collector ） 。一旦有一個腳位的開洩極導通接地，則整條線都為低電位，這種現象稱作 wired-AND 運作 ；如同邏輯 AND 運算，需要共接的腳位都是 1 （開洩極斷路），該條線的電位才是 1 。如果沒有開洩極的腳位，可以使用具內部高接電阻的腳位，當要輸出 1 時，則設定該腳位為高接型輸入腳；而輸出為 0 時，則改設定為輸出腳並輸出 0 的值。 圖 1. I 2 C 傳輸裝置接線 [1] I 2 C 通訊協定 為使說明部分更簡潔，首先介紹幾個名詞： 位元傳輸協定 當 master 要跟 slave 溝通時，會先有個起始條件（ start condition ）的訊號，結束時也會送出終止條件（ stop condition ）訊號。起始條件訊號
Post a Comment
Read more

【Arduino】Timers, Registers, and Fast PWM Mode

由於Arduino預設的PWM控制方法僅有500Hz（好像還有另一個），想要知道怎樣才可以調整成其他頻率，以此做記錄。 先說明Timer設定方式、PWM Mode，之後會在Arduino上實做。 如果對_BV()沒有概念，可以參考 【Arduino I/O Ports】Control under avr-libc 這篇文章。
1 comment
Read more

Emart Sunny Sale: 3D Shadow QR Code

　　Emart是韓國連鎖超市，近期他們發現中午12:00到下午1:00的銷售量會明顯減少，為了提高銷售量他們製作出了帶有日晷概念的3D QR code。
Post a Comment
Read more