Apple Division

簡易題敘

有 $n$ ( $1 \le n \le 20$ ) 個蘋果，每個蘋果都有一個重量 $p_i$ ( $1 \le p_i \le 10^9$ ) ，要把所有蘋果分到兩個籃子裡面，兩籃子的重量越接近越好，求兩籃子重量最小差。

範例測資：

輸入

5
3 2 7 4 1

輸出

概念講解

這題的 $n$ 最多到 $20$ ，所以最多會有 $2^{20}$ 種狀況，大約是 $10^6$ ，所以用位元枚舉窮舉每種可能是可行的！

首先，要有一個變數紀錄目前最小的重量差，我們稱它為 ans，因為要求最小值所以先初始化為一個極大的數。

int ans = 1e18;

用 a 陣列紀錄第 i 個蘋果的重量，tot 紀錄所有蘋果的總重。

int n, tot = 0, a[21];

因為每顆蘋果都可以選擇選或不選，所以總共有 $2^n$ 種不同的選法，0代表不選，1代表選，以範例測資為例，我們用二進位表示的話就是從00000到11111跑過每種可能的選法。

for (int i = 0; i < (1 << n); i++)

用 while 迴圈跑到分完所有蘋果為止，開個變數 tot1 記第 $1$ 個籃子的重量，每次檢查這個二進位的最後一位 ( 當前這一位 ) ，如果是1的話 num & 1 就會是1，代表要選這顆，tot1 += a[idx]，否則就是0，不用算他的重量。好比說00101指的就是選第 $1$ 顆跟第 $3$ 顆的情況，tot1等於 $10$ 。

while (num != 0) {
    if ((num & 1) == 1) {
        tot1 += a[idx];
    }
    idx++;
    num >>= 1;
}

而第二個籃子的重量 tot2 就是我們之前計算過的總重減去剛剛算的 tot1 ，答案取最小值，就大功告成啦！

int tot2 = tot - tot1;
ans = min(ans, abs(tot2 - tot1));

範例程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int ans = 1e18;
    int n, tot = 0, a[21];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        tot += a[i];
    }
    for (int i = 0; i < (1 << n); i++) {
        int num = i, idx = 0, tot1 = 0;
        while (num != 0) {
            if ((num & 1) == 1) {
                tot1 += a[idx];
            }
            idx++;
            num >>= 1;
        }
        int tot2 = tot - tot1;
        ans = min(ans, abs(tot2 - tot1));
    }
    cout << ans << '\n';
}