題目連結: https://zerojudge.tw/ShowProblem?problemid=b116
# 內容
假設有 N 個正整數 A [1], A [2],..., A [N]，我們要在每一個數字之
前加入 + 號或 - 號使得它們的總和為 0。例如: 1, 2 及 3，我們可以得到
(-1)+(-2)+(+3)=0；但是對於 2, 2 及 1 則無法透過加入 + 號或 - 號使得它
們的總和為 0。
請你寫一個程式來判斷任意 N 個正整數是否可以透過加入 + 號或
- 號使得它們的總和為 0。
# 解題思路
問題能被化減成將 N 個正整數平均分成兩堆，若能剛好分成等值的兩堆即為 Yes，否則 No
所以，可以運用 DP 的方式，在這群數字中湊出 sum/2，即為 Yes
# 程式碼
#include <iostream> | |
#include <cstring> | |
using namespace std; | |
int t, m, total, half, dp[25005], num[105]; | |
int main(){ | |
while (cin>>t>>m){ | |
while(t--){ | |
total = 0; | |
for (int i = 0; i < m; i++){ | |
cin >> num[i]; | |
total += num[i]; | |
} | |
half = total / 2; | |
memset(dp, 0, sizeof(dp)); | |
for (int i = 0; i < m; i++){ | |
for (int j = half; j >= num[i]; j--){ | |
dp[j] = max(dp[j], dp[j-num[i]] + num[i]); | |
} | |
} | |
if(total == 2*dp[half])cout<<"Yes\n"; | |
else cout<<"No\n"; | |
} | |
} | |
} |
