alan23273850 的刷題筆記
a522: 12455 - Bars
Tags: subset-sum
出處：https://zerojudge.tw/ShowProblem?problemid=a522
提交：https://zerojudge.tw/Submissions?problemid=a522&account=allllllan123456
問題：給你 $p\in[1,20]$ 個正整數，問你有沒有辦法從中挑出一些數字使得其和剛好為給定的 $n\in[0,1000]$。
解法：此乃子集和問題，解法可參考本站介紹該問題的頁面。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int T; cin >> T;
6 while (T--) {
7 int n, p; cin >> n >> p;
8 bool dp[1001] = {false}; dp[0] = true;
9 while (p--) {
10 int v; cin >> v;
11 for (int i=n; i>=v; i--)
12 dp[i] |= dp[i-v];
13 }
14 cout << (dp[n] ? "YES\n" : "NO\n");
15 }
16 return 0;
17}