# 【題解】ZeroJudge a522: 12455 – Bars

Virtual Judge: https://vjudge.net/problem/UVA-12455

#include <iostream>
using namespace std;
int a[20];

int main() {
int cases, target, sticks, num, tmp, i;
bool flag;
while (cin >> cases){
while (cases--){
cin >> target;
cin >> sticks;
for (int i = 0; i < sticks; i++){
cin >> a[i];
}
num = 1;
for (int i = 1; i < sticks; i++){
num <<= 1;
num++;
}
flag = false;
for (int _i = 0; _i <= num; _i++){
tmp = 0;
i = _i;
for (int j = 0; j < sticks; j++){
if (i & 1) tmp += a[j];
i >>= 1;
}
if (tmp == target){
flag = true;
break;
}
}
if (flag) cout << "YES\n";
else cout << "NO\n";
}
}
}

Python 程式碼 (credit: Amy Chou)

# 0 ≤ t ≤ 50，表示測資的筆數
t = int(input())
for iter1 in range(t):
# 每筆測資三行，第一行有一個數字 n, 0 ≤ n ≤ 1000，表示我們所要的長度。
n = int(input())
# 第二行有一個數字 p, 1 ≤ p ≤ 20，表示我們所擁有的金屬棒的數量。
p = int(input())
# 第三行有 p 個數字，表示 p 根金屬棒的長度。
P = list(map(int, input().split()))

dp = [0 for i in range(n+1)]
for i in P:
for j in range(n, 0, -1):
if (j >= i):
dp[j] = max(dp[j], dp[j - i] + i)

if (dp[n] == n):
print("YES")
else:
print("NO")