
JSで動的計画法を利用して部分和問題を解く
2022-02-207 min read
目次
概要
動的計画法を利用して部分和問題を計算した際のメモです。(AtCoder用)
動的計画法
動的計画法について
↓
部分和
部分和問題について
↓
ソース
動的計画法を行う関数
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
}
Recommends
javascriptで累積和を解く
2022-02-27
JSで動的計画法を利用して部分和問題を解く
2022-02-20
JavaScriptで優先度付きキューを実装する
2021-08-01
next_permutationをJSで実装する
2021-07-22
GatsbyからNext.jsへのサイト移行
2022-04-04
NextJSでDevToysのようなものを作成した
2022-02-22
NestJSアプリケーションをwebpackでBundle
2022-02-20
[Next.js] Warning: Assign arrow function to a...
2022-02-13
[JS]ラジアンから度数に度数からラジアンに変換する
2021-06-13
JS/TSのclassでclass名を取得する
2021-05-24
JSで32ビット符号付き整数に対してのビット演算でハマった
2021-02-17
JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
2021-02-16
プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
2021-02-09
JSでサブネットマスクの計算
2021-02-04
Typescriptに入門した
2021-01-04
New Posts
[AWS CDK]ECS FargateでNestJSで作成したRESTfull APIデ...
2022-05-24
[AWS CDK]S3 CloudFront OAI Route53 構成 で NextJ...
2022-05-23
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
GatsbyからNext.jsへのサイト移行
2022-04-04
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
[AWS CDK] Cognito を構築
2022-03-04
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
javascriptで累積和を解く
2022-02-27
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
NextJSでDevToysのようなものを作成した
2022-02-22
JSで動的計画法を利用して部分和問題を解く
2022-02-20
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
OpenCVのMatのタイプ一覧表
2018-11-25
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
Macでターミナルからポートスキャンを行う方法。
2018-12-09
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
Date
▶︎
2022 年 (23)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
Author