与えられた配列 A = [a₁, a₂, ..., aₙ] から、いくつかの要素を選んで和を K にする 。
ただし、同じ位置の要素は1回まで使える（0-1制約） 。
和が作れない場合は -1 を出力し、
作れる場合は選んだ要素数が最小となる組み合わせ を出力します。 アルゴリズム：動的計画法（0-1ナップサックDP） A = [1, 3, 2, 2, 1]
K = 4
dp[0][0] = 0 （和が0のときは0個選ぶ）
dp[0][k≠0] = ∞ （初期は不可能）
k（和）
0
1
2
3
4
dp[0][k]
0
∞
∞
∞
∞
使わない場合： dp[1][k] = dp[0][k]使う場合： dp[1][k+1] = min(dp[1][k+1], dp[0][k] + 1)
k（和）
0
1
2
3
4
dp[1][k]
0
1
∞
∞
∞
dp[2][3] = min(dp[2][3], dp[1][0]+1) => 1個（3だけ選択）
dp[2][4] = min(dp[2][4], dp[1][1]+1) => 2個（1+3）
k（和）
0
1
2
3
4
dp[2][k]
0
1
∞
1
2
dp[3][2] = min(∞, dp[2][0]+1) => 1個（2）
dp[3][3] = min(1, dp[2][1]+1) => 1個（既にあるのでそのまま）
dp[3][4] = min(2, dp[2][2]+1) => 2個（2+2）
k（和）
0
1
2
3
4
dp[3][k]
0
1
1
1
2
同様に更新されるが、dp[3][k]が最適なので更新なし（同じ値が入る）
使わない場合：dp[4][k]をコピー
使う場合：
dp[5][1] = min(1, dp[4][0]+1) => 1
dp[5][2] = min(1, dp[4][1]+1) => 1
dp[5][3] = min(1, dp[4][2]+1) => 1
dp[5][4] = min(2, dp[4][3]+1) => 2
k（和）
0
1
2
3
4
dp[5][k]
0
1
1
1
2
dp[5][4]=2 →「和4を作るため、prev[5][4]=3」dp[5][3]=1 →「和3を作るため、prev[5][3]=1」
選んだ数：3,1
（順番は逆でも良い）
初期化 dp[0][0]=0
↓
for i=1..N:
for k=0..K:
- 使わない場合 dp[i+1][k]=dp[i][k]
- 使う場合 dp[i+1][k+A[i]]=min(dp[i+1][k+A[i]], dp[i][k]+1)
↓
復元（prev配列から逆追跡）
↓
出力（個数 + 選んだ要素）
i-1
|
┌──┴──┐
使わない 使う
↓ ↓
dp[i][k] dp[i][k+A[i]] = min(dp[i][k+A[i]], dp[i-1][k]+1)
項目
値
時間計算量
O(N × K)
空間計算量
O(N × K)
const startTime = process . hrtime . bigint ( ) ;
...（処理） . . .
const endTime = process . hrtime . bigint ( ) ;
console . error ( `Time: ${ ( endTime - startTime ) / 1e6 } ) ;
const used = process . memoryUsage ( ) ;
console . error ( `Memory: ${ Math . round ( used . heapUsed / 1024 ) } ) ;
処理
内容
DP配列
和kを作る最小個数を保持
prev配列
選んだ要素を復元するための履歴
復元処理
和Kから逆に辿る