アルゴリズム Rubyメモ

二分探索

計算量 O(log_2n)

def binary_search(size, value)
  arr = (1..size).to_a

  left = 0
  mid = 0 #=> 中央の値
  right = arr.last

  loop do
    mid = (left + right) / 2
    if arr[mid] == value
      return "Found"
    elsif arr[mid] < value
      left = mid
    else #arr[mid] > value
      right = mid
    end
  end
end

しゃくとり法

計算量 O(n)

長さnの数列a0,a1,,,,anと整数Sが与えれています。
連続する部分列で、その総和がS以上となるようなもののうち、最小の長さを求めなさい。
また、そのときの総和S
を求めなさい。
解が存在しない場合は０を出力しなさい。

LENGTH = 5
SUM = 11
ARRAY = [1,2,3,4,5]

total = 0
res = LENGTH
go = 0
back = 0

arr = []

loop do
  while go < LENGTH && total < SUM
    total += ARRAY[go]
    go += 1
  end
  break if total < SUM
  res = [res, go - back].min
  arr << total
  total -= ARRAY[back]
  back += 1
end

if res > LENGTH
  puts "0"
else
  puts "総和は#{arr.min}, 最小の長さは#{res}"
end

深さ優先探索

計算量 O(2^n)

整数a_1,a_2、、、、、a_nが与えられた時、その中からいくつか選び、その和をKにすることができるか判定しなさい

N = 4
ALLAY_VALUE = [1,2,4,7]
SUM = 13

def depth_first_search(val, total)
  if val == N
    total == SUM
  elsif depth_first_search(val + 1, total)
    true
  elsif depth_first_search(val + 1, total + ALLAY_VALUE[val])
    true
  else
    false
  end
end

if depth_first_search(0, 0)
  puts "Yes"
elsif
  puts "No"
end

動的計画法

# 値を再利用しながら解いていく、動的計画法
M = gets.to_i
N = gets.to_i
arr_key = Array.new(N)
arr_value = Array.new(N)
min_cost = 0

N.times do |i|
  key, value = gets.split(" ").map(&:to_i)
  arr_key[i] = key
  arr_value[i] = value
  min_cost += value
end

dp = Hash.new
dp[0] = 0

N.times do |ind|
  dp_tmp = dp.clone
  dp.each do |key, value|
    total_key = key + arr_key[ind]
    total_value = value + arr_value[ind]

    unless dp_tmp.has_key?(total_key)
      dp_tmp[total_key] = total_value
    end

    if total_key >= M && min_cost > total_value
      min_cost = total_value
    end
  end

  dp = dp_tmp
end

p min_cost