題目敘述:https://zerojudge.tw/ShowProblem?problemid=a522
Virtual Judge: https://vjudge.net/problem/UVA-12455
解題想法:利用位元組合(每根金屬棒拿或不拿,即 0 或 1)計算所有可能的長度和
#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)
用上述做法會TLE,改用DP。
# 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")