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.
N W
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)
end
#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
end
(1..w).each do |i|
if i != weight && dp[i] != 0 && i+weight <= w
dp[i+weight] += value
end
end
end
#Output maximum value
puts dp.max
Recommended Posts