bit全探索で動的計画法を実装する JavaScript

2019-06-10
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0atcoder%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95dp%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97javascript
    

目次

概要

AtCoderとかをやっていると、 動的計画法(DP)、部分和といった問題とかに遭遇したりしますが、1から実装しようとすると面倒だったりします。 (というよりも、再帰処理で書くのが苦手だったりするからです...) こんな時に、ビット演算を用いてパターンをひとまず網羅してから実装することがあります。 ここではJSを例に紹介します。

サンプル1

シフト演算で実装する コード

function main(n) {
    for (let bit = 0; bit < (1 << n); bit++) {
        let row = []
        for (let i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                row.push(i)
            }
        }
        console.log(row)
    }
}
main(4);

このコードの結果は次のようになります。 結果

0
1
0,1
2
0,2
1,2
0,1,2
3
0,3
1,3
0,1,3
2,3
0,2,3
1,2,3
0,1,2,3

部分和の問題を解いてみます。

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

function fetchBitPattern(n, f) {
    for (let bit = 0; bit < (1 << n); bit++) {
        let row = []
        for (let i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                row.push(i)
            }
        }
        f(row)
    }
}

function main() {
    const Q = [3, 7, 8, 12, 13, 18]
    const A = 27
    fetchBitPattern(Q.length, (bit) => {
        let s = 0
        let tmp = []
        for (let i = 0; i < bit.length; i++) {
            s += Q[bit[i]]
            tmp.push(Q[bit[i]])
        }
        if (s === A) {
            console.log(tmp)
        }
    })
}

main()
[7,8,12]

と表示されます。

サンプル2

toStringメソッドで実装する。

function main(n) {
    for (let i = 0; i < Math.pow(2, n); i++) {
        let row = []
        let t = i.toString(2)
        for (let j = t.length; j < n; j++) {
            t = '0' + t
        }
        t = t.split('').map(Number)
        for (let j = 0; j < t.length; j++) {
            if (t[j] === 1) {
                row.push(j)
            }
        }
        console.log(row)
    }
}
main(4)

このコードの結果は次のようになります。

3
2
2,3
1
1,3
1,2
1,2,3
0
0,3
0,2
0,2,3
0,1
0,1,3
0,1,2
0,1,2,3

同じく部分和問題を解いてみます。

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

function fetchBitPattern(n, f) {
    for (let i = 0; i < Math.pow(2, n); i++) {
        let row = []
        let t = i.toString(2)
        for (let j = t.length; j < n; j++) {
            t = '0' + t
        }
        t = t.split('').map(Number)
        for (let j = 0; j < t.length; j++) {
            if (t[j] === 1) {
                row.push(j)
            }
        }
        f(row)
    }
}

function main() {
    const Q = [3, 7, 8, 12, 13, 18]
    const A = 27
    fetchBitPattern(Q.length, (bit) => {
        let s = 0
        let tmp = []
        for (let i = 0; i < bit.length; i++) {
            s += Q[bit[i]]
            tmp.push(Q[bit[i]])
        }
        if (s === A) {
            console.log(tmp)
        }
    })
}

main();
[7,8,12]

と表示されます。

見ての通り、どちらのサンプルもをゴリゴリとループで片付けているので必ずしも効率的ではないと思います。

参考

https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361

https://ja.stackoverflow.com/questions/49702/%E3%83%93%E3%83%83%E3%83%88dp%E3%81%AE%E6%80%9D%E8%80%83%E5%9B%9E%E8%B7%AF%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6

    
s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV

関連記事

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

JavaScriptで幅優先探索 (bfs) を実装する
bfsソースコード 前提 bfs関数 テストコード JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。 AtCoderの問題を参考にしています bfsソースコード 前提 bfs 関数の定義について 引数 table…

JavaScriptでbig-integerでできること
定数 メソッド abs add, plus and bitLength compare compareTo compareAmb divide, over divmod equals, eq greater, gt greaterOrEquals, geq…

ソースコードレビューのポイントをまとめる
ソースコードレビュー時のポイントを各所のブログから集めてまとめました。以下 https://gist.github.com/s-yoshiki/9e446d69cf388703a4711f7e69cba173

0埋め・ゼロ埋め処理 のコードJavaScript
サンプル コード 呼び出す 説明 参考 追記 JavaScriptで 0埋め / ゼロ埋め / zero埋め 処理を行うサンプルコード サンプル コード 呼び出す 説明 記事タイトルが…

順列・組み合わせ のサンプルコード JS [permutation] [combination]
順列 - permutation サンプルコード Usage 組み合わせ - combination サンプルコード Usage 順列(permutation) と 組み合わせ(combination) のサンプルコードをJavaScript…

うるう年を求めるプログラム JavaScript
閏年の条件 サンプルコード 判定関数 21世紀のうるう年を算出する うるう年を求める実装メモです。 閏年の条件 閏年の条件は以下の通りとなります。 https://www.nao.ac.jp/faq/a0306.html サンプルコード 判定関数 2…

MonacoEditor + Vue を使ってエディタを実装
紹介 セットアップ Vue vue-monaco Usage サンプルコード ポイント テーマカラーについて エディタのリサイズ エディタの変更の検知 Vue + MonacoEditorでJS…

async awaitで画像を読み込み canvasに描画 JavaScript
async サンプルコード async await Promise を使ってブラウザにアップロードした画像をcanvasに非同期で描画するサンプルの紹介です。 onloadメソッド縛りで実装すると非同期地獄になりますが、async await…

最新の投稿

GitHub Actions で Gatsby をビルドし Amazon S3 にデプロイする
GitHub Actions について あらかじめ準備しておくもの AWS IAM ユーザを環境変数にセットする workflowの記述 ビルド バッジを利用する 終わりに 参考にしたところ Gatsbyで作った静的サイトを、GitHub Actions…

cloudinaryによる画像ファイルの管理 はじめてみる
目的 cloudinary について 他のサービスとの比較 料金プラン アカウントの登録 利用してみる ダッシュボード 画像の編集 APIベースでのアクセス 感想 参考 画像の管理や配信、さらには加工といった事ができるsaas型のcloud…

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

Vue.jsで作成された、ちょっと面白くて役立ちそうなサービス
UIコンポーネント VueSocial CKEditor 5 Vue.Draggable Vuetable 2 vuejs-datepicker Kalendar Vue Apexcharts Vue.js Google Charts vue-cart WebIDE…

GitHubのリポジトリをGitLabに同期する GitLabのミラーリング機能
GitLabのミラーリングについて GitHubのリポジトリをGitLabに反映する その他 参考 GitLabのミラーリング機能によりGitHubなどの外部のリポジトリとのミラーリングを行うことができます。 これを使ってGitHub…

WordPressやめます Gatsbyに移行しました
これまでのWordPress運用 なぜWordPressを捨てるのか? なぜGatsbyを利用するのか? gatsbyについて WordPressから記事の救出 移行対象記事の抽出 記事の置換 Gatsbyテーマの作成 Gatsby…

WordPressのDBから記事データを抽出する
WordPressのDB関連図 公開記事一覧の取得 タグ・カテゴリの取得 サムネイルの取得 おまけ: PHPスクリプト化しました 参考にしたところ WordPressにため込んだデータMarkdown化しGatsby…

ハイフンとかマイナスとかダッシュとか

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

GolangをCGIとして実行する
環境 golang パッケージ ソースと実行 ビルドとサーバ実行 標準ライブラリのみ Golang を CGIとして実行する際のメモ 環境 golang パッケージ 以下のモジュールを利用しています。 github.com/gorilla/mux…

Tags

Dates

© 2020   404 motivation not found