アルゴリズム

今日解いた問題2

彩色問題 アリ本の93ページ 隣接したりノードが同じ色にならないように色をぬる。 今回は2色で塗ることができるかという問題 特に2色でぬれるグラフを2部グラフという コードで言うと0が塗ってないノードなので下の2つを繰り返す感じ 隣接したノードjが0…

今日解いた問題

分割数はいまいちわかっていない 最長増加部分列問題 自分(i)より小さい部分問題を解いていけばできる N = 5 A = [4, 2, 3, 1, 5].freeze $dp = Array.new(N, 1) def solve N.times do |i| i.times do |j| $dp[i] = [$dp[j] + 1, $dp[i]].max if A[i] > A[j]…

ナップザック問題

久しぶりにナップザック問題書いてみたら思いの外時間がかかって辛かった N = 4 W = 5 ITEMS = [[2, 3], [1, 2], [3, 4], [2, 2]].freeze # [重さ, 価値] INF = 10000000 # 全探索 def dfs(i, w) return 0 if i == N b = dfs(i + 1, w) a = w - ITEMS[i][0] …

LIS(最長増加部分列)を全探索,メモ化でといた

アリ本にのっていたLISを全探索,メモ化でも解いたので覚え書き LISは与えられた配列をaとするとi>jかつa[i]>a[j]を満たす部分列のこと DPバージョン dp[i]はiより前のjの中で制約(i>j かつ a[i]>a[j])を満たすdp[j]の一番大きい値の+1となる. 例えば,a = …