JSで動的計画法を利用して部分和問題を解く

目次

1. 概要
2. 動的計画法
3. 部分和
4. ソース
5. おまけ-typescript用

概要

動的計画法を利用して部分和問題を計算した際のメモです。(AtCoder用)

動的計画法

動的計画法について

↓

動的計画法 - Wikipedia

部分和

部分和問題について

↓

部分和問題 - Wikipedia

ソース

動的計画法を行う関数

function solve(data, num) {
  const dp = Array.from(
    new Array(data.length + 1),
    () => new Array(num + 1).fill(0),
  );
  for (let col = 0; col < data.length; col++) {
    for (let row = 0; row < num + 1; row++) {
      if (row < data[col]) {
        dp[col + 1][row] = dp[col][row];
      } else {
        dp[col + 1][row] = Math.max(
          dp[col][row],
          dp[col][row - data[col]] + data[col],
        );
      }
    }
  }
  return dp[data.length][num] === num;
}

利用方法は以下です。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

const arr = [3, 7, 8, 12, 13, 18];
console.log(solve(arr, 27) ? '存在する' : '存在しない');

おまけ: TypeScript用

TypeScript用のソースです。

const solve = (data: Array<number>, num: number) => {
  const dp = Array.from(
    new Array(data.length + 1),
    () => new Array(num + 1).fill(0),
  );
  for (let col = 0; col < data.length; col++) {
    for (let row = 0; row < num + 1; row++) {
      if (row < data[col]) {
        dp[col + 1][row] = dp[col][row];
      } else {
        dp[col + 1][row] = Math.max(
          dp[col][row],
          dp[col][row - data[col]] + data[col],
        );
      }
    }
  }
  return dp[data.length][num] === num;
};