louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=24943

題目大意:  問2個人拿古董，價值相差最小為多少

思路:  01背包問題，用一個陣列紀錄那些重量可以達到，每個古董都放，放這個古董的話dp[價值-古董價值]為True，則這個價值為True。基底價值0為True.

之後枚舉全部重量看那些能達到，計算最小差。這題竟然是困難(?)，感覺跟前面題型都差不多。

代碼:  

#include <bits/stdc++.h>
#define N 55
using namespace std;

int arr[N];
int main()
{
    int n, k;
    cin >> n;
    while(n--){
        bool dp[N*10000] = {};
        cin >> k;
        int sum = 0;
        for(int i = 0; i < k; ++i){
            cin >> arr[i];
            sum += arr[i];
        }
        dp[0] = 1;
        for(int i = 0; i < k; ++i){
            for(int j = sum; j >= arr[i]; --j){
                dp[j] |= dp[j-arr[i]];
            }
        }
        int mn = INT_MAX;
        for(int i = 1; i <= sum; ++i){
            if(dp[i]) mn = min(abs(i - (sum-i)), mn);
        }
        cout << mn << endl;
    }
    return 0;
}