src/dp/knapsack.cr

• View this file on GitHub
• Last update: 2022-04-16 07:49:21+00:00

Verified with

• test/dp/knapsack01_test.cr
• test/dp/knapsack_test.cr

Code

module DP
  extend self

  def knapsack(weight_limit : Int32, value : Array(Int), weight : Array(Int32))
    raise ArgumentError.new unless value.size == weight.size
    n = value.size
    (0...n).each_with_object([typeof(value.first).zero] * weight_limit.succ) do |i, dp|
      (0..weight_limit - weight[i]).each do |j|
        dp[j + weight[i]] = Math.max(dp[j + weight[i]], dp[j] + value[i])
      end
    end
  end

  def knapsack01(weight_limit : Int32, value : Array(Int), weight : Array(Int32))
    raise ArgumentError.new unless value.size == weight.size
    n = value.size
    (0...n).each_with_object([typeof(value.first).zero] * weight_limit.succ) do |i, dp|
      (0..weight_limit - weight[i]).reverse_each do |j|
        dp[j + weight[i]] = Math.max(dp[j + weight[i]], dp[j] + value[i])
      end
    end
  end
end

module DP
  extend self

  def knapsack(weight_limit : Int32, value : Array(Int), weight : Array(Int32))
    raise ArgumentError.new unless value.size == weight.size
    n = value.size
    (0...n).each_with_object([typeof(value.first).zero] * weight_limit.succ) do |i, dp|
      (0..weight_limit - weight[i]).each do |j|
        dp[j + weight[i]] = Math.max(dp[j + weight[i]], dp[j] + value[i])
      end
    end
  end

  def knapsack01(weight_limit : Int32, value : Array(Int), weight : Array(Int32))
    raise ArgumentError.new unless value.size == weight.size
    n = value.size
    (0...n).each_with_object([typeof(value.first).zero] * weight_limit.succ) do |i, dp|
      (0..weight_limit - weight[i]).reverse_each do |j|
        dp[j + weight[i]] = Math.max(dp[j + weight[i]], dp[j] + value[i])
      end
    end
  end
end

Back to top page