動的計画法（ナップサック問題） - アルゴリズム講習会
動的計画法（ナップサック問題） 動的計画法とナップサック問題について解説します。 動的計画法とは 直接計算すると大きな時間がかかってしまう問題に対し、途中の計算結果をうまく再利用することで計算効率を上げる手法のこと。 「途中の計算結果を再利用」＝「同じ計算をしない」ということ 難しいように見えて考え方自体は単純 ICPC国内予選でもC問題～F問題くらいに何かしらの形で2,3題ほどでます 英語では「Dynamic Programming」と呼び、略して「DP」と呼ぶことが多いです。 動的計画法で効率的に解ける問題の一つに、ナップサック問題というものがあります。 ナップサック問題 ナップサック問題は、価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？ という問題です。 具体的には、以下の図のようになります。ナ
自動お絵かきロボを作る（その2） | fladdict
作成中の自動絵画プログラム。どうやら、みんなは「フォトショのフィルター的なモノ」を想像してるみたい。実はこのお絵かきロボ、一筆づつ丁寧に色を乗せていったりする。むっちゃ時間かかる。 アルゴ的には、遺伝アルゴリズムとA/Bテストの中間のようなロジックで動いてます。無数のパターンを一筆ごとに総当たりし、うまい感じに色がのった場合のみ採用みたいな。そんなわけで800px程度の大きさでも、1毎仕上げるのに2-6時間ぐらいかかります。 先にざっくり全体を下塗りしていくようにチューニング。 こちらが最新バージョン。ついに「主題でない部分に塗り残しや、筆跡などを多めに残す：チューニングが完成。 静物画の写真を、油絵に変換したもの。油絵っぽい写真を変換すれば、油絵になる。 ニワトリ。ちょっと目のコントラストが薄くて検出できなかった・・・失敗。それ以外はいい感じ。 サル。毛の質感はもう文句がない。あとは粗密
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
