[Competition Pro] Solve the knapsack problem with Ruby


There are $ N $ pieces of luggage and a knapsack with an allowable weight of $ W $. The $ i (1 ≤ i ≤ N) $ th package is $ v_i $ in value and $ w_i $ in weight. When choosing a set of packages so that the sum of the weights is less than $ W $, find the maximum sum of the values. However, you can only select the same luggage once.


v1 w1
v2 w2
vN wN


#Receive input
nw = gets.chomp.split.map(&:to_i)
n = nw[0]
w = nw[1]
vw_a = []
n.times do
    vw_a << gets.chomp.split.map(&:to_i)

#An array that stores the maximum value for each weight
dp = Array.new(w+1, 0)

vw_a.each do |vw|
    value = vw[0]
    weight = vw[1]
    if weight <= w && value > dp[weight]
        dp[weight] = value
    (1..w).each do |i|
        if i != weight && dp[i] != 0 && i+weight <= w
            dp[i+weight] += value

#Output maximum value
puts dp.max


Recommended Posts

[Competition Pro] Solve the knapsack problem with Ruby
[At Coder] Solve the ABC183 D problem with Ruby
Solve the N + 1 problem with Ruby on Rails: acts-as-taggable-on
[At Coder] Solve the ABC182 D problem with Ruby
Solving the knapsack problem with dynamic programming
I tried to solve the problem of "multi-stage selection" with Ruby
[Beginner] Let's solve AtCoder problem with Ruby while looking at the article!
I tried to solve the tribonacci sequence problem in Ruby, with recursion.
Solve the Discrete Logarithm Problem with an arbitrary mod
Solve Google problems with Ruby
Let's solve the FizzBuzz problem!
[Ruby] problem with if statement
[Beginner's point of view] I tried to solve the FizzBuzz problem "easily" with Ruby!
Programming with ruby (on the way)
Solve with Ruby AtCoder ABC177 D UnionFind
Ruby problem ⑦
[At Coder] Introducing Competitive Pro with Ruby
I tried to solve the tribonatch sequence problem in Ruby (time limit 10 minutes)
Publish the app made with ruby on rails
Manage the version of Ruby itself with rbenv
AtCoder ABC127 D hash to solve with Ruby 2.7.1
[Ruby] Exclude duplicate elements with the uniq method.
Determine the current page with Ruby on Rails
[Java] Try to solve the Fizz Buzz problem
Finding pi with the Monte Carlo method? (Ruby)
I checked the number of taxis with Ruby
ruby search problem
[Ruby] FizzBuzz problem
ruby API problem
[Ruby] FizzBuzz problem
[Ruby] Ruby API problem
ruby API problem
Solve Ruby TGIF
Feel the basic type and reference type easily with ruby
Feel the basic type and reference type easily with ruby 2
I tried to solve the Ruby karaoke machine problem (there is an example of the answer)