切換
舊版
前往
大廳
主題

ZeroJudge - e179: Runningman - 目標金額 解題心得

Not In My Back Yard | 2019-05-24 22:52:50 | 巴幣 0 | 人氣 133

題目連結:


題目大意:
給定三正整數 n 、 k 、 target (1 ≦ n ≦ 20 , 1 ≦ k ≦ n ,0 ≦ target ≦ 2 × 10 ^ 7),代表有 n 個錢袋,要從中挑出 k 個使得總金額恰好為 target 。

接著有 n 個正整數 i (0 ≦ i ≦ 10 ^ 6),代表其中一個錢袋內含的金額。

若可以從 n 個錢袋中挑出 k 個使得總金額剛好為 target ,則輸出「YES」;反之,輸出「NO」。



範例輸入:
5 2 3
1 2 3 4 5
5 3 3
1 2 3 4 5
5 4 10
1 2 3 4 5
5 1 0
1 2 3 4 5


範例輸出:
YES
NO
YES
NO


解題思維:
這題類似,但是只能從中挑 k 個。因此深度優先搜尋(DFS)的遞迴停止條件要多判斷現在挑了幾個錢袋。如果挑了 k 個以上,則回到上一層的遞迴堆疊。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作