日期:2025年7月18日
ZeroJudge 題目連結:a981. 求和問題
解題想法
這題要用遞迴窮舉所有的組合,輸出其中符合條件的組合,並且要適當地剪枝,節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼,最後一筆測資超時。
Python 程式碼
最後一筆測資超時。
def solve():
import sys
lines = sys.stdin.readlines()
head = 0
while head < len(lines):
n, m = map(int, lines[head].split()) # 讀取數量 n,要找的加總 m
nums = sorted(list(map(int, lines[head+1].split()))) # 讀取候選的數值
head += 2 # 從 lines 讀取資料的索引值
choice = [False]*n # 是否選這個數字
have_ans = False # 是否有解
### 主要的解題過程,輸入目前檢測的 nums 索引值,加總 ###
def backtrack(curr, total):
nonlocal have_ans # 這樣才能改變外層 have_ans 的值
if total == m: # 有解,印出選擇的數字,結束遞迴
have_ans = True
solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
sys.stdout.write(f"{solution}\n")
return
if curr == n or total > m: return # 已出界或是目標為負值,結束遞迴
choice[curr] = True # 選此項
backtrack(curr + 1, total + nums[curr]) # 遞迴,索引值加 1,total 加上此項的值
choice[curr] = False # 回溯,不選此項
backtrack(curr + 1, total) # 遞迴,索引值加 1,total 不變
### End of backtrack ###
backtrack(0, 0) # 從索引值 0、加總 0 開始
if not have_ans: sys.stdout.write("-1\n") # 如果無解,印出 -1
if __name__ == "__main__":
solve()
C++ 程式碼
使用時間約為 1.2 s,記憶體約為 252 kB,通過測試。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, m; // 讀取數量 n,要找的加總 m
vector<int> nums (30); // 候選的數值
vector<bool> choice (30); // 是否選這個數字
bool have_ans; // 是否有解
/* 主要的解題過程,輸入目前檢測的 nums 索引值,加總 */
void backtrack(int curr, int total) {
if (total == m) { // 有解,印出選擇的數字,結束遞迴
have_ans = true;
bool first = true; // 是否為首項
for(int i=0; i<n; i++) { // 掃過 n 個數字
if (choice[i]) { // 如果有選此項
if (!first) printf(" "); // 不是首項,先印空格
first = false; // 只要 choice[i] 為 true,此項改成 false
printf("%d", nums[i]);
}
}
puts(""); // 換行
return;
}
if (curr == n || total > m) return; // 已出界或是目標為負值,結束遞迴
choice[curr] = true; // 選此項
backtrack(curr + 1, total + nums[curr]); // 遞迴,索引值加 1,total 加上此項的值
choice[curr] = false; // 回溯,不選此項
backtrack(curr + 1, total); // 遞迴,索引值加 1,total 不變
}
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
nums.resize(n); // 依照 n 改變長度
choice.resize(n);
for(int i=0; i<n; i++) {
scanf("%d", &nums[i]);
choice[i] = false;
}
sort(nums.begin(), nums.end());
have_ans = false; // 是否有解
backtrack(0, 0); // 從索引值 0、加總 0 開始
if (!have_ans) puts("-1"); // 如果無解,印出 -1
}
return 0;
}
沒有留言:
張貼留言