部分和問題 1（DP）

今回は paiza のDPの「部分和問題 1」に挑戦！

またまたDPを新しいテーマで学んでいく！

問題概要

• 1 から n まで番号のついたn 個のおもり がある。

• おもり i の重さは a_i である。

• これらのおもりから いくつかを選んで、その合計が ちょうど x になるようにできるかどうかを判定せよ。

• ただし、同じおもりを2回以上使うことはできない。

• 出力
  • 可能なら “yes”
  • 不可能なら “no”

入力例:

5 19 // n x
7
18
5
4
8

出力例:

yes

✅ OK例：

const rl = require('readline').createInterface({ input:process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const [n, x] = lines[0].split(' ').map(Number);
    const a = lines.slice(1).map(Number);
    a.unshift(0);

    const dp = Array(x+1).fill(false);

    // おもりを選ばなければ、重さの和を0とすることができる
    dp[0] = true;
    

    // おもり i までのおもりを使って
    for (let i = 1; i <= n; i++) {
        // 重さの和を j とすることができるか？
        for (let j = x; j >= a[i]; j--) {
            if (dp[j-a[i]]) {
                dp[j] = true;
            }
        }
    }
    
    
    if (dp[x]) {
        console.log('yes');
    }
    else {
        console.log('no');
    }
});

🔍 処理の流れ

• 初期化
  • 配列 dp を用意（サイズ = x+1）
  • dp[0] = true（重さ0は常に作れる）

• 各おもりを順番に処理
  • 1つずつ このおもりを使って「重さの和を j とすることができるか？」を考える

• 更新（降順ループ）
  • j = x から a[i] まで降順で回す
  • もし dp[j – a[i]] が true なら このおもりを使って足すと 重さの和 を j にできる　→ dp[j] = true に更新
  • 降順にすることで「同じおもりを同じループ内で複数回使う」ことを防げる

• 答え判定
  • 最後に dp[x] が true なら「作れる」→ yes
  • false なら「作れない」→ no

🔍 true の内容

n = 5, x = 19
おもり = [7, 18, 5, 4]

// ※if (dp[j-a[i]] === true) dp[j] = true;

📌 a[i] を足すことによって 重さ j になれば a[i]のおもりを使って重さの和 jとすることができるので 、true ということ。

→ dp[j] は おもりを何個か選んで重さの和 j をつくれるか。

📌 dp[j-a[i]] が false であれば、重さの和 j-a[i] を作れる おもりの組み合わせがなかったということなので、そもそも a[i] を"足せない"。

📌 dp[j-a[i]] が true であれば、当然 j-a[i] に a[i] を足すと j になるということで、1つ目の📌に戻って true。

🔍 下↓　trueの内容

• 最初：合計 0 だけが true (dp[0] = true) 。 true = {0}

• 7 を使う → {0} に 7 を足せるので → {0, 7}
  • 例：j = 7, a[i] = 7
    ↪︎ dp[7-7] = dp[0] = true → dp[7] = true

• 18 を使う → {0,7} に 18 を足せる → {0, 7, 18, 25}
  • 例：j = 25, a[i] = 18 →
  • ↪︎ dp[25 – 18] = dp[7] = true → dp[25] = true

• 5 を使う → {0,7,18,25} に 5 を足せる → {0, 7, 12, 18, 23, 25, 30}

• 4 を使う → {0,7,12,18,23,25,30} に 4 を足せる → {0, 4, 7, 11, 12, 16, 18, 22, 23, 25, 26, 30, 34}
  • (7 + 4 = 11)

• 8 を使う → {0, 4, 7, 11, 12, 16, 18, 22, 23, 25, 26, 30, 34}に8を足せる →
  ↪︎ {8, 12, 15, 19, 20, 24, 26, 30, 31, 33, 34, 38, 42}
  • （11 + 8 = 19）

→ このとき 19 が含まれている！
→ よって答えは “yes”。

🔍 降順ループの理由

逆に a_i から x へ 増やす方向にループを回すと正しい答えが求められない可能性がある。

◯前提

n=1, a₁=5, x=10

使えるおもりは「5」の1個だけ。正しい答えは no（同じおもりを2回は使えない）。

◯昇順ループ（j = a[i] → x）だとNG

• 初期: dp[0] = true, 他は false
• j=5 のとき: dp[5] → dp[0] が true なので dp[5]=true
• j=10 のとき: dp[10] → dp[10-5]= dp[5] を参照 　　　　　　　　　　
  → 直前に更新した dp[5]=true を使ってしまい dp[10]=true
  → 「同じ5のおもり を 2回 使えた」ことになり、yes（誤り）。

◯降順ループ（j = x → a[i]）なら OK

• 初期: dp[0]=true
• j=10 のとき: dp[10-5] = dp[5] はまだ false → 変化なし
• j=5 のとき: dp[5-5] = dp[0] が true なので dp[5]=true（ここで初めて true）
  → j=10 はもう通過済みなので参照されない。dp[10]=false のまま
  → no（正しい）。

◯結論:

昇順に回すと「同一おもりを同ループ内で複数回使う」誤更新が起きる

🗒️ まとめ・めも

• 初期化
  • dp[0] = true（重さ0は必ず作れる）
• おもりを順に処理
  • 各おもり a[i] について、
    j = x から a[i] まで 降順ループ
• 更新
  • もし dp[j – a[i]] = true なら
    → dp[j] = true にする
• 判定
  • 最後に dp[x] = true なら Yes、そうでなければ No

📌 ポイントは「降順ループで、同じおもりを1回しか使わないようにすること」。

→ 降順に回せば「各おもりは1回しか反映されない」ので正しい判定になる

僕の失敗談(´;ω;｀)と解決法🐈