Il y a des bagages de $ N $ et un sac à dos d'un poids autorisé de $ W $. Le paquet $ i (1 ≤ i ≤ N) $ th a une valeur de $ v_i $ et un poids de $ w_i $. Lorsque vous choisissez un ensemble de bagages pour que la somme des poids soit inférieure à $ W $, trouvez la somme maximale des valeurs. Cependant, vous ne pouvez sélectionner qu'une seule fois le même bagage.
N W
v1 w1
v2 w2
:
vN wN
#Recevoir des entrées
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
#Un tableau qui stocke la valeur maximale pour chaque poids
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
#Valeur maximale de sortie
puts dp.max
Recommended Posts