Knapsack - Exercism in Elixir

문제 보기

각 물건의 무게와 가치가 주어졌을 때, 최대 무게 maximum_weight 안에서 가져갈 수 있는 물건의 최대 가치를 구하는 문제였다. 코딩 테스트 바닥에서 말하는 완전탐색 타입의 문제. 조금 더 최적화할 여지는 있어보이긴 하는데, 파이프라인이 제법 깔끔하게 만들어져서 만족하고 끝내기로 했다.

defmodule Knapsack do
  @doc """
  Return the maximum value that a knapsack can carry.
  """
  @spec maximum_value(items :: [%{value: integer, weight: integer}], maximum_weight :: integer) ::
          integer
  def maximum_value(items, maximum_weight) do
    max = Integer.pow(2, length(items))
    1..(max-1)
    |> Enum.map(fn i ->
      Integer.to_string(i, 2)
      |> String.pad_leading(length(items), "0")
      |> String.graphemes()
      |> Enum.zip(items)
      |> Enum.filter(fn {i, _item} -> i == "1" end)
      |> Enum.map(fn {_i, item} -> item end)
    end)
    |> Enum.filter(fn items ->
      items
      |> Enum.map(fn item -> item.weight end)
      |> Enum.sum()
      |> Kernel.<=(maximum_weight)
    end)
    |> Enum.map(fn items ->
      items
      |> Enum.map(fn item -> item.value end)
      |> Enum.sum()
    end)
    |> Enum.max(&>=/2, fn -> 0 end)
  end
end