Elixirで動的計画法（DP）を実装してみた（Goとの比較つき）

package main

import (
    "fmt"
    "math"
    "time"
)

func main() {
    var (
        input     = [][]int{[]int{2, 3}, []int{5, 85}, []int{1, 2}, []int{3, 6}, []int{2, 1}, []int{1, 3}}
        inputHuge = [][]int{}
    )
    for i := 0; i < 50000; i++ {
        inputHuge = append(inputHuge, input...)
    }

    var (
        start   = time.Now()
        res     = knapsack(inputHuge, 9)
        elapsed = time.Since(start)
    )
    fmt.Printf("elapsed:%v, res:%+v\n", elapsed, res)
}

func knapsack(items [][]int, maxW int) int {
    var (
        N  = len(items)
        dp = make([][]int, N+1)
    )
    for i := range dp {
        dp[i] = make([]int, maxW+1)
    }

    for i := 0; i < N; i++ {
        var (
            w = items[i][0]
            v = items[i][1]
        )
        for j := 0; j < maxW+1; j++ {
            if w <= j {
                dp[i+1][j] = int(math.Max(float64(v+dp[i][j-w]), float64(dp[i][j])))
            } else {
                dp[i+1][j] = dp[i][j]
            }
        }
    }

    return dp[N][maxW]
}

$ go run dp/main.go 
elapsed:71.8844ms, res:97

defmodule Dp do
  def solve([[]], _), do: 0
  def solve([[w, _]], max_w) when w > max_w, do: 0
  def solve([[w, v]], max_w) when w <= max_w, do: v

  def solve([[w, _] | items], max_w) when w > max_w do
    solve(items, max_w)
  end

  def solve([[w, v] | items], max_w) when w <= max_w do
    max(v + solve(items, max_w - w), solve(items, max_w))
  end
end

# これだと重すぎて死ぬのでメモ化とか必要
input = [[2, 3], [5, 85], [1, 2], [3, 6], [2, 1], [1, 3]]
input_huge = 1..200 |> Enum.reduce([], fn _, acc -> acc ++ input end)

Dp.solve(input_huge, 9) |> IO.inspect()

defmodule Dp do
  def solve(items, max_w) do
    :ets.new(__MODULE__, [:set, :protected, :named_table])

    0..max_w |> Enum.each(fn w -> insert(0, w, 0) end)

    for {[w, v], i} <- Enum.with_index(items), j <- 0..max_w do
      if w <= j do
        res = max(lookup(i, j - w) + v, lookup(i, j))
        insert(i + 1, j, res)
      else
        insert(i + 1, j, lookup(i, j))
      end
    end

    lookup(length(items), max_w)
  end

  defp insert(i, w, res) do
    :ets.insert(__MODULE__, {{i, w}, res})
    res
  end

  defp lookup(i, w) do
    [{_, res}] = :ets.lookup(__MODULE__, {i, w})
    res
  end
end

input = [[2, 3], [5, 85], [1, 2], [3, 6], [2, 1], [1, 3]]
input_huge = 1..50000 |> Enum.reduce([], fn _, acc -> acc ++ input end)

:timer.tc(Dp, :solve, [input_huge, 9]) |> IO.inspect()

$ elixir dp_ets.exs
{3685769, 97}

iex> table = %{ 0 => 0..9 |> Enum.reduce( %{}, & Map.put( &2, &1, 2 ) ) }
%{
  0 => %{
    0 => 2,
    1 => 2,
    2 => 2,
    3 => 2,
    4 => 2,
    5 => 2,
    6 => 2,
    7 => 2,
    8 => 2,
    9 => 2
  }
}
iex> table[ 0 ][ 5 ]
2

defmodule Dp do
  def solve_map(items, max_w) do
    table = %{0 => 0..max_w |> Enum.reduce(%{}, &Map.put(&2, &1, 0))}

    table =
      Enum.reduce(Enum.with_index(items), table, fn {[w, v], i}, table ->
        add_i =
          0..max_w
          |> Enum.reduce(table[i], fn j, tmp ->
            add_j =
              if w <= j do
                max(table[i][j - w] + v, table[i][j])
              else
                table[i][j]
              end

            Map.put(tmp, j, add_j)
          end)

        Map.put(table, i + 1, add_i)
      end)

    table[length(items)][max_w]
  end
end

input = [[2, 3], [5, 85], [1, 2], [3, 6], [2, 1], [1, 3]]
input_huge = 1..50000 |> Enum.reduce([], fn _, acc -> acc ++ input end)

:timer.tc(Dp, :solve_map, [input_huge, 9]) |> IO.inspect()

$ elixir dp/dp7.exs
{1670776, 97}