[Competition Pro] Résolvez les problèmes de sac à dos avec Ruby

problème

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.

contribution

N W
v1 w1
v2 w2
:
vN wN

Répondre

#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

commentaire

Recommended Posts

[Competition Pro] Résolvez les problèmes de sac à dos avec Ruby
[At Coder] Résolvez le problème ABC183 D avec Ruby
[At Coder] Résolvez le problème ABC182 D avec Ruby
Résoudre le problème du sac à dos avec une planification dynamique
J'ai essayé de résoudre le problème de la "sélection multi-étapes" avec Ruby
[Débutant] Résolvons le problème d'AtCoder avec Ruby en regardant l'article!
J'ai essayé de résoudre le problème de la séquence Tribonacci en Ruby, avec récurrence.
Résolvez le problème du logarithme discret avec un mod arbitraire
Résolvons le problème FizzBuzz!
[Ruby] problème avec l'instruction if
Programmation avec ruby (en route)
Résolution avec Ruby AtCoder ABC177 D Union Find
Problème de rubis ⑦
[Chez Coder] Présentation de Competitive Pro avec Ruby
J'ai essayé de résoudre le problème de la séquence Tribonacci en Ruby (temps limite 10 minutes)
Publiez l'application avec ruby on rails
Gérez la version de Ruby elle-même avec rbenv
AtCoder ABC127 D hash à résoudre avec Ruby 2.7.1
Déterminez la page actuelle avec Ruby on Rails
[Java] Essayez de résoudre le problème de Fizz Buzz
J'ai vérifié le nombre de taxis avec Ruby
problème de recherche de rubis
[Ruby] Problème de FizzBuzz
Problème d'API ruby
Problème d'API ruby
Résoudre Ruby TGIF
Ressentez facilement le type de base et le type de référence avec ruby
Ressentez facilement le type de base et le type de référence avec ruby 2
J'ai essayé de résoudre le problème de la machine à karaoké Ruby (il y a un exemple de réponse)