bitDP
ある集合Sについての値を計算する前に、集合Sから要素を一つ取り除いたものについての値が確定して欲しい。
つまり「要素を一つ取り除いたもの」という関係を有向辺とみなしたグラフをトポロジカルソートしてその順に計算したい。
この時、集合の「要素iを含む」と、整数の「i番目のビットが1」を対応づけると、整数の自然な順序がグラフのトポロジカルソートにもなっている。
mask = 1 << i としてi \in S:
S & mask その時のS / i:
S ^ mask pythondef solve_tsp(num_vertex, distance):
import sys
INF = sys.maxsize
SIZE = 2 ** num_vertex
memo = [[INF] * num_vertex for _i in range(SIZE)]
memo[0][0] = 0
for subset in range(1, SIZE):
for v in range(num_vertex):
for u in range(num_vertex):
mask = 1 << u
if subset & mask:
memo[subset][v] = min(
memo[subset][v],
memo[subset ^ mask][u] + distance[u][v])
return memo[-1][0]Related Pages
- →指数時間アルゴリズム×岩田_陽一×巡回セールスマン問題×最大クリーク問題×幅×グリッドグラフ×pathwidth×半分全列挙×最大独立集合問題×fptアルゴリズム×最小頂点被覆問題×有界探索木×カーネライズ×シュタイナー木問題×包除原理×ハミルトンパス×グラフ彩色問題×彩色数×高速ゼータ変換×畳込み×完全マッチングの個数×完全マッチング×color_coding×k-cycle×bandwidth×cut_&_count×iterative_compression→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
- →past3×past3n×past3o×past1m×past1k×最小共通祖先×past1l×クラスカル法×past2h×past2i×past2j×PAST2K×最小費用流×past2n×平面走査法×PAST3M×巡回セールスマン問題×past2m×past4m×past2l×past4n×past2o×past4o×past1o→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]