サイゼリヤで1000円あれば最大何kcal摂れるのか

saize.rb

# coding: utf-8
require 'csv'

budget = 1000
menu = []
# https://raw.githubusercontent.com/hodaka0714/saize_calory_maxmization/master/menu.csv
CSV.foreach('menu.csv') do |row|
  menu << row
end

dp = Array.new(menu.size + 1) { Array.new(budget + 1, -1) }

def solv(dp, menu, yen, i)
  return 0 if i.zero?
  return dp[i][yen] if dp[i][yen] != -1
  ret = 0
  ret = [solv(dp, menu, yen, i - 1), ret].max
  if yen - menu[i-1][4].to_i >= 0
    ret = [solv(dp, menu, yen - menu[i-1][4].to_i, i-1) + menu[i-1][5].to_i,
           ret].max
  end
  dp[i][yen] = ret
  ret
end

def disp(dp, menu, yen, i)
  return if yen <= 0
  return if i <= 0
  if yen >= menu[i-1][4].to_i &&
     dp[i][yen] == dp[i-1][yen - menu[i-1][4].to_i] + menu[i-1][5].to_i
    puts "%-25s%5s円%5skcal" % [menu[i-1][1], menu[i-1][4], menu[i-1][5]]
    yen -= menu[i-1][4].to_i
  end
  disp(dp, menu, yen, i-1)
end

ret = solv(dp, menu, budget, menu.size)
disp(dp, menu, budget, menu.size)
puts "#{ret}kcal"

ラージライス 219円 454kcal
アーリオ・オーリオ(Wサイズ) 574円 1120kcal
ポテトのグリル 199円 366kcal
1940kcal