Es gibt $ N $ Gepäckstücke und einen Rucksack mit einem zulässigen Gewicht von $ W $. Das $ i (1 ≤ i ≤ N) $ -te Paket hat einen Wert von $ v_i $ und ein Gewicht von $ w_i $. Wenn Sie einen Gepäcksatz so auswählen, dass die Summe der Gewichte weniger als $ W $ beträgt, ermitteln Sie die maximale Summe der Werte. Sie können jedoch nur einmal dasselbe Gepäck auswählen.
N W
v1 w1
v2 w2
:
vN wN
#Eingaben empfangen
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
#Ein Array, das den Maximalwert für jedes Gewicht speichert
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
#Maximalwert ausgeben
puts dp.max
Recommended Posts