Rod Cutting Problem

Q: Pourquoi le découpage de tiges est-il un problème de sac à dos non borné ?

Considérez chaque morceau de longueur k comme un objet de poids k et de valeur prices[k-1] , disponible en quantité illimitée, et la tige comme un sac de capacité n qu’il faut remplir exactement. La meilleure valeur totale des objets est alors le meilleur prix pour la tige.

Q: Comment trouver où couper la tige ?

Stockez, pour chaque longueur, le premier morceau k qui a donné son meilleur prix. Commencez à la longueur n : coupez un morceau de la longueur stockée, passez à la longueur restante et répétez jusqu’à atteindre 0. Les morceaux forment un plan optimal.

MoyenProgrammation dynamique

+10

Tu disposes d’une tige de longueur n, où n = prices.length. Un morceau de longueur k se vend au prix de prices[k-1]. Tu peux découper la tige en autant de morceaux de longueurs entières que tu le souhaites, ou la vendre en un seul morceau. Retourne la somme maximale que tu peux gagner en vendant toute la tige.

Fonction

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] est le prix d'une pièce de longueur k ; la tige a une longueur de prices.length
Renvoieinteger: le plus d’argent que toute la tige peut rapporter

Contraintes

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Exemples

Entrée: prices = [2, 5, 7, 8]
Sortie: 10
Explication: Deux morceaux de longueur 2 se vendent 5 + 5 = 10. Vendre la tige entière rapporte 8, et un morceau de 1 plus un morceau de 3 rapporte 2 + 7 = 9.

Pour aller plus loin

Et si tu peux couper la tige au maximum m fois ? Que doit alors savoir chaque entrée du tableau ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une barre de longueur n peut être découpée de 2^(n-1) façons. Tu n’as jamais besoin de toutes les connaître : quelle que soit la première pièce, le reste est une barre plus courte qui pose la même question. Il n’existe donc que n+1 réponses, une par longueur, et les calculer de la plus courte à la plus longue prend O(n²) étapes.

Essaie toutes les longueurs possibles pour le premier morceau

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Quel que soit le plan, la pièce à l’extrémité gauche a une longueur k comprise entre 1 et la longueur de la tige et rapporte prices[k-1] ; le reste du plan consiste à couper une tige de longueur length-k. Ainsi, best(length) vaut 0 lorsque la longueur est 0 et, sinon, correspond à la plus grande valeur de prices[k-1] + best(length-k) parmi toutes les valeurs de k, où k = length signifie que la tige est vendue entière. Chaque plan comporte une première pièce, donc ce maximum couvre tous les plans.

Chaque appel se ramifie en tous les cas de longueur inférieure, donc le nombre d’appels double à chaque unité de longueur : une tige de 40 donne environ 2^40, soit 10^12, appels.

Algorithme

Écris best(length), qui renvoie 0 pour une longueur de 0.
Pour chaque premier morceau k de 1 à length, calcule prices[k-1] + best(length-k).
Renvoie la plus grande de ces valeurs.
Renvoie best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Meilleur prix pour chaque longueur, de la plus courte à la plus longue

Intuition

La récursion recalcule les mêmes valeurs : best(2) est demandé par best(3), best(4) et toutes les longueurs de tige supérieures. Il n’y a que n+1 longueurs, alors calcule chacune une seule fois dans un tableau best. Une longueur ne lit que des longueurs plus courtes ; remplir le tableau de 0 vers le haut signifie donc que chaque valeur est prête au moment où elle est lue.

Avec [2, 5, 7, 8] : best[1] vaut 2, best[2] est le plus grand de 2 + 2 et 5, soit 5, best[3] vaut 7, et best[4] est le plus grand de 2 + 7, 5 + 5, 7 + 2 et 8, soit 10.

Contrairement au sac à dos 0/1, best[len-k] peut déjà contenir des morceaux de longueur k, et c’est ce que tu veux, puisqu’une longueur peut être découpée autant de fois que tu le souhaites. La longueur len essaie d’abord len premiers morceaux : n(n+1)/2 étapes au total, soit environ 5 × 10^5 pour une tige de 1000.

Algorithme

Créez best avec n + 1 entrées, toutes à 0.
Pour chaque length de 1 à n, essayez chaque première pièce k de 1 à length.
Calculez prices[k-1] + best[length-k] et conservez la valeur la plus élevée dans best[length].
Retournez best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

Pièges et cas limites

Lire prices[k] pour une longueur k. Cela attribue à chaque morceau une taille supérieure d’une unité et dépasse la fin à k = n ; utilisez prices[k-1].
Omettre k = length, le morceau non coupé. Alors best[1] reste à 0, et [1, 3, 8] rapporte 3 au lieu de 8.
Couper de manière gloutonne en fonction du meilleur prix par unité. Avec [2, 7, 11, 13], la longueur 3 rapporte le plus par unité, mais 11 pour ce morceau plus 2 pour le reste donne 13, tandis que deux morceaux de longueur 2 en rapportent 14.
Mémoriser les résultats de haut en bas en Python. La récursion s’imbrique toujours aussi profondément que la longueur de la tige : une tige de 1000 entraîne 1001 appels imbriqués, ce qui dépasse la limite par défaut de 1000. Remplissez le tableau de bas en haut.

Questions fréquentes4

Quelle est la complexité temporelle du problème de découpe de tige ?

Le tableau prend un temps O(n²) et utilise O(n) de mémoire : la longueur len essaie len premières pièces, soit n(n+1)/2 essais au total. Sans réponses mémorisées, la récursion effectue exactement 2^n appels pour une tige de longueur n, puisque chaque longueur appelle toutes les longueurs inférieures.

Pourquoi le découpage de tiges est-il un problème de sac à dos non borné ?

Considérez chaque morceau de longueur k comme un objet de poids k et de valeur prices[k-1], disponible en quantité illimitée, et la tige comme un sac de capacité n qu’il faut remplir exactement. La meilleure valeur totale des objets est alors le meilleur prix pour la tige.

Comment trouver où couper la tige ?

Stockez, pour chaque longueur, le premier morceau k qui a donné son meilleur prix. Commencez à la longueur n : coupez un morceau de la longueur stockée, passez à la longueur restante et répétez jusqu’à atteindre 0. Les morceaux forment un plan optimal.

Comment la solution change-t-elle si chaque coupe coûte de l’argent ?

Vendre la tige entière ne nécessite aucune coupe, tandis que tout autre premier morceau ajoute une coupe. Ainsi, best[len] devient la plus grande valeur entre prices[len-1] et la plus grande valeur de prices[k-1] + best[len-k] - cost pour k inférieur à len. Le reste du tableau reste identique.

def cutRod(prices):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

prices = [2, 5, 7, 8]

Résultat attendu