a276: 又分糖果囉

內容 ：
    再分糖果吧！
    你一開始有 n 包糖果，每包糖果裡面有若干顆，想要公平的分給 2 個人
    所謂公平就是指這兩個人有的糖果數量的差越小越好。

輸入說明 ：
    多組輸入，以EOF作為結束
    每組測試資料的第一行是一個正整數 n ，第二行有 n 個數字 mi 以空格隔開
    1 <= n <= 20
    1 <= mi <= 1000000

輸出說明 ：
    輸出兩人糖果數量的的差。

範例輸入 ：
4
1 3 7 8
5
1 2 4 9 4

範例輸出 ：
1
0

提示 ：
    第一組：(3,7) 和 (1,8)
    第二組：(4,4,2) 和 (1,9)

概念講解 ：
    可以試著用01背包問題來解決。
    不懂什麼是01背包問題沒關係，我們只需要知道對這一包糖果我們有兩個選擇，那就是拿和不拿，我們以範例一為例，並假設左邊是不拿，右邊是拿，接著看看下面我辛苦畫的圖吧!


對其中一個人而言，每包糖果都有兩個選擇，那就是拿和不拿

                                                                              start

                                                        不拿 |─────────────|拿

                                                                0                                   1                 第一包糖果 有1個糖果

                                                 不拿 |────|拿           不拿 |─────|拿

                                                         0           0+3                  1            1+3      第二包糖果 有3個糖果 

剩下的請允許我偷懶一下          |───|      |───|            |───|       |───|
拿與不拿就省略不寫                 0        7     3     10          1       8     4       11   第三包糖果 有7個糖果 
                                                  |─|     |─|    |─|    |─|        |─|     |─|    |─|     |─|
                                                 0  8   7 15 3 11 10 18    1  9   8 16 4 12  11 19 第四包糖果 有8個糖果


    看到最下面的16個數字了嗎?這些就是所有糖果的組合情況，也就是代表說這些是兩個人中的其中一個人拿到的所有情形，既然算出了其中一個人的糖果數，那另一個人的糖果數相信你一定可以算得出來，最後把糖果數差最小的印出來就行了。

程式碼 ：

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

int min,n,total,mi[20];

void isGet(int temp, int index)
{
    if(index == n)
    {
        temp = total - temp - temp;
        if(temp < 0)
            temp = -temp;
        if(temp < min)
            min = temp;
        return ;
    }
    if(min == 0)
        return ;
    isGet(temp, index+1);
    isGet(temp + mi[index], index+1);
}

int main()
{
    int i;
    
    while(scanf("%d",&n)==1)
    {
        total = 0;
        min = 99999999;
        for(i=0; i<n; i++)
        {
            scanf("%d",&mi[i]);
            total += mi[i];
        }
        isGet(0, 0);
        printf("%d\n",min);
    }
    
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=a276