Skip to content

A18

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

A18

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
A18(BitSet).js
A18(BitSet).js
 
 
A18(DP).go
A18(DP).go
 
 
A18(DP).js
A18(DP).js
 
 
A18(DP).php
A18(DP).php
 
 
A18(DP).ts
A18(DP).ts
 
 
README.md
README.md
 
 

README.md

例題：4 11 (N = 4, S = 11, A = [3, 1, 4, 5]) をDPテーブルで解説

この問題は、4枚のカードの中からいくつか選んで合計を11にできるかを判定するものです。
動的計画法（DP）を使って、どのように解くのかを 図で詳しく説明 します。

1. DPテーブルの作成

dp[i][j] を 「i枚目までのカードを使って合計 j を作れるか？」 という意味で定義します。
初期状態では、何も選ばない場合 dp[0][0] = true だけが true になります。

DPテーブルの大きさは N+1 × S+1 になります。

2. DPテーブルの遷移

カード ( A[i] ) を 「選ぶ」「選ばない」 の2通りで次の状態を決めます。

  • カード i を選ばない場合
    → dp[i+1][j] = dp[i][j]（前の状態を引き継ぐ）
  • カード i を選ぶ場合（ j + A[i] ≤ S の場合のみ）
    → dp[i+1][j + A[i]] = dp[i][j]（ j が作れるなら j + A[i] も作れる）

3. DPテーブルの遷移を図で表す

初期状態 (i = 0)

i\j 0 1 2 3 4 5 6 7 8 9 10 11
0 ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
  • 何も選ばなければ合計 0 は作れる (dp[0][0] = true)
  • 他はすべて false （まだ作れない）

カード1枚目 (A[0] = 3) を考慮

i\j 0 1 2 3 4 5 6 7 8 9 10 11
0 ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
1 ✅ ❌ ❌ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
  • dp[1][3] = true（0 から 3 を足して作れる）

カード2枚目 (A[1] = 1) を考慮

i\j 0 1 2 3 4 5 6 7 8 9 10 11
0 ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
1 ✅ ❌ ❌ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
2 ✅ ✅ ❌ ✅ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌
  • dp[2][1] = true（0 から 1 を足して作れる）
  • dp[2][4] = true（3 から 1 を足して作れる）

カード3枚目 (A[2] = 4) を考慮

i\j 0 1 2 3 4 5 6 7 8 9 10 11
0 ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
1 ✅ ❌ ❌ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
2 ✅ ✅ ❌ ✅ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌
3 ✅ ✅ ❌ ✅ ✅ ✅ ❌ ✅ ✅ ❌ ❌ ❌
  • dp[3][5] = true（1 から 4 を足して作れる）
  • dp[3][7] = true（3 から 4 を足して作れる）
  • dp[3][8] = true（4 から 4 を足して作れる）

カード4枚目 (A[3] = 5) を考慮

i\j 0 1 2 3 4 5 6 7 8 9 10 11
0 ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
1 ✅ ❌ ❌ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌
2 ✅ ✅ ❌ ✅ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ❌
3 ✅ ✅ ❌ ✅ ✅ ✅ ❌ ✅ ✅ ❌ ❌ ❌
4 ✅ ✅ ❌ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ❌
  • dp[4][6] = true（1 から 5 を足して作れる）
  • dp[4][9] = true（4 から 5 を足して作れる）
  • dp[4][10] = true（5 から 5 を足して作れる）

👉 dp[4][11] = false なので、答えは "No"

4. 結論

入力 4 11 3 1 4 5 の場合、 合計 11 を作る方法はないため No と出力。

5. 実装

function subsetSumExists(N, S, A) {
    let dp = Array.from({ length: N + 1 }, () => Array(S + 1).fill(false));
    dp[0][0] = true;

    for (let i = 0; i < N; i++) {
        for (let j = 0; j <= S; j++) {
            if (dp[i][j]) {
                dp[i + 1][j] = true;
                if (j + A[i] <= S) {
                    dp[i + 1][j + A[i]] = true;
                }
            }
        }
    }

    console.log(dp[N][S] ? 'Yes' : 'No');
}

6. まとめ

✅ DPテーブルを作成し、「選ぶ・選ばない」の2択を考える
✅ 計算量 O(N × S) で 60 × 10000 = 600000 なら間に合う
✅ DPテーブルを視覚化すると理解しやすい！