部分和《DP・漸化式》

DPメニュー【部分和問題 1 〜 4 】

問題【STEP: 1】部分和問題 1
Task
 n 個のおもりを何個か選んで重さの和が x にできるかどうか判定してね。

【部分和問題 1】コード

reader.on('close', () => {
   const [n, x] = lines[0].split(' ').map(Number);
   const a = [];  // おもりの重さ 
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));  // aに各おもりの重さを保存
   }
   const dp  = new Array(x + 1).fill(false);  // index グラムにできるかどうかの真偽値
   dp[0] = true;  // おもり 0 個の場合 O グラムにできる
   for (let i = 0; i < n; i++) {  // おもりを 1 〜 n 個使って…
      if(dp[x]){  // dp[x] がtrueなら…
         break;  // 調べる必要なし
      }
      for (let j = x; j >= a[i]; j--) {  // jグラム(j <= x >= a[i])にできるか？…
         if (dp[j - a[i]]) {  // a[i]を追加する前 がtrueなら…
            dp[j] = true;  // a[i]を追加すれば jグラムになる
         }
      }
   }
   console.log(dp[x] ? 'yes' : 'no');
});
hogeちゃんの画像

おもりを何個か選んで重さの和が x にできるかどうかの判定。なので dp の値は index グラムにできるかどうかの真偽値になっています。

top
問題【STEP: 2】部分和問題 2
Task
 n 個のおもりを何個か選んで重さの和を x にする方法が何通りあるか求めてね。

【部分和問題 2】コード

reader.on('close', () => {
   const [n, x] = lines[0].split(' ').map(Number);
   const a = [];  // おもりの重さ
   const dp = new Array(x + 1).fill(0);  // indexグラムになるパターン数
   dp[0] = 1;  // 0 グラムになるパターン数は 1   
   const mod = 1000000007;
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));  // a に各おもりの重さを保存
   }
   for (let i = 0; i < n; i++) {  // おもりを 1 〜 n 個使って…
      for (let j = x; j >= a[i]; j--) {  // jグラム(j <= x >= a[i])にできるか？…
         dp[j] += dp[j - a[i]];  // jグラムになるパターン数にj-a[i]グラムになるパターン数を加算
         dp[j] %= mod;
      }
   }
  console.log(dp[x]);
});
hogeちゃんの画像

おもりを何個か選んで重さの和が x となるようにする方法が何通りあるか。なので dp の値はindexグラムにする方法のパターン数…。

top
問題【STEP: 3】部分和問題 3
Task
n 個のおもりを何個か選んで重さの和が x にする方法のうち おもりの個数の最小値は?

【部分和問題 3】コード

reader.on('close', () => {
   const [n, x] = lines[0].split(' ').map(Number);
   const a = [];
   const dp = new Array(x + 1).fill(n + 1);  // indexグラムになるおもりの個数の最小値をn以上の値で初期化
   dp[0] = 0;  //  O グラムの場合は０個
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));  // aに各おもりの重さを保存
   }
   for (let i = 0; i < n; i++) {
      for (let j = x; j >= a[i]; j--) {
         dp[j] = Math.min(dp[j], dp[j - a[i]] + 1); 
// jグラムになる最小個数 = (既に求まっている値, j-a[i]グラムになる最小個数 + 1個) の内小さい方
      }
   }
  console.log(dp[x] === n + 1 ? -1 : dp[x]);
// dp[x]が初期値のままなら -1 更新されていれば dp[x] を出力
});
hogeちゃんの画像

重さの和が x となるようにする方法のうち 選ぶおもりの個数の最小値を出力。なので dp の値はindexグラムにするために選ぶ重りの個数の最小値…。

top
問題【FINAL】部分和問題 4
Task
n 種類(無限個)のおもりを何個か選んで重さの和が x にできるかを判定してね。

【部分和問題 4】コード

reader.on('close', () => {
   const [n, x] = lines[0].split(' ').map(Number);
   const a = [];  // おもりの重さ
   for (let i = 1; i <= n; i++) {
      a.push(Number(lines[i]));  // a に各おもりの重さを保存
   }
   const dp  = new Array(x + 1).fill(false);  // index グラムにできるかどうかの真偽値
   dp[0] = true;  // おもり 0 個の場合 O グラムにできる
   for (let i = 0; i < n; i++) {  // おもりを 1 〜 n 個使って…
      if(dp[x]){  // dp[x] がtrueなら…
         break;  // 調べる必要なし
      }  
      for (let j = a[i]; j <= x; j++) {
         if (dp[j - a[i]]) {  // a[i]を追加する前 がtrueなら…
            dp[j] = true;  // a[i]グラム加算すれば jグラムになる
         }
      }
   }
   console.log(dp[x] ? 'yes' : 'no');
});
hogeちゃんの画像

 n 種類のおもりが無限個存在し 任意のおもりを任意の個数使うことがでるなので ループを回す順序が a[i] → x になりました。

top

コメント