d021: Q_2_10 子集合的和(折半枚舉)
Tags : ch2
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-02-17 20:52

Content

輸入 $n$ 個正整數 $A_1, A_2 ... A_n$,另外給了一個整數 $P$,請計算 $A$ 中元素各種組合中,其和最接近 $P$ 但不超過 $P$ 的和是多少。

每個元素可以選取或不選取但不可重複選,$A$ 中的數字可能重複。$A_i$ 與 $P$ 均不超過 $2^{60}$,$0 < n \le 38$。

Input

 第一行是 $n$ 與 $P$ ,第二行 $n$ 個整數是 $A_i$,同行數字以空白間隔。

Output

 最接近 $P$ 但不超過 $P$ 的和。

Sample Input #1
5 17
5 5 8 3 10
Sample Output #1
16
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.5s , <1K
公開 測資點#3 (20%): 1.5s , <1K
公開 測資點#4 (20%): 1.5s , <1K
Hint :
Tags:
ch2
出處:
Prof. Wu [管理者:
ktlai (K.我已霸榜.Tlai)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」