【部分和】部分和問題

今回は paiza のDPで「【部分和】部分和問題 4」に挑戦！

この問題で DP の最終問題まで制覇！

問題概要

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

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

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

• 同じおもりを複数回使うことができる。

• 出力

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

入力例:

5 10 // n x
9    // a_1
3
4
11
8    // a_n

出力例:

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);
    dp[0] = true;
    
    for (let i = 1; i <= n; i++) {
        for (let j = a[i]; j <= x; j++) {
            if (dp[j-a[i]]) dp[j] = true;
        }
    }
    
    if (dp[x]) console.log('yes');
    if (!dp[x]) console.log('no');
});

• dp の定義

  • dp[j] = true なら「重さ j を作れる」。
  • 初期値: dp[0] = true（0は何も使わず作れる）。

• 漸化式

  • もし dp[j - a[i]] === true なら dp[j] = true。
    （おもり a[i] を使って j を作れる、という意味）

• ループ順序の違い

  • 使えるのが1回だけ（部分和問題1~3）→ j を 「降順ループ」 する（重複を防ぐ）。
  • 無限回使える（この問題）→ j を 「昇順ループ」 する（同じ重さを繰り返し足せるように）。

• 出力

  • dp[x] === true → "yes"
  • そうでなければ "no"

✅ コードの要点

for (let i = 1; i <= n; i++) {
    for (let j = a[i]; j <= x; j++) {
        if (dp[j - a[i]]) dp[j] = true;
    }
}

• 昇順ループなので、dp[j] を更新する時点で、同じおもりを複数回使った場合の結果も反映される。

• 例：重さ 3 のおもり
  → dp[3] = true → 次の j=6 の時にもう一度使える → dp[6] = true。

🗒️ まとめ

• 初期化

  • dp[0] = true（重さ0は必ず作れる）

• おもりを順に処理

  • 各おもり a[i] について、
  • j = a[i] から x まで 昇順ループ

• 更新

  • もし dp[j – a[i]] = true なら
  • → dp[j] = true にする

• 判定

  • 最後に dp[x] = true なら yes、そうでなければ no

📌 ポイント：

• 「おもり無限」→ 昇順ループ
• 「おもり1回限り」→ 降順ループ

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