Fractional Knapsack

Q: Quelle est la complexité temporelle du problème du sac à dos fractionnaire ?

Trier les éléments par valeur par poids coûte O(n log n) et le remplissage se fait en un seul passage, donc le coût total est de O(n log n) avec un espace de O(n) pour l’ordre. Rechercher l’élément le plus dense à chaque tour coûte O(n²) .

Q: Comment résoudre le problème du sac à dos fractionnaire sans nombres à virgule flottante ?

Avec des poids positifs, a / b > c / d revient au même test que a × d > c × b , donc comparez les densités par produit en croix. La meilleure valeur est un nombre entier plus une fraction, values[i] × room / weights[i] pour l’objet fractionné ; une division entière donne donc exactement la réponse arrondie à l’entier inférieur.

MoyenGlouton Tri

+10

Tu as n objets. L’objet i vaut values[i] et pèse weights[i]. Ton sac peut contenir un poids total d’au plus capacity, et tu peux prendre n’importe quelle partie d’un objet : une partie de l’objet i qui pèse w vaut values[i] × w / weights[i].

Écris une fonction nommée fractionalKnapsack qui renvoie la valeur totale maximale que le sac peut contenir, arrondie à l’entier inférieur.

Fonction

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: la valeur de chaque élément
weightsinteger-array: le poids de chaque élément
capacityinteger: le poids maximal que le sac peut contenir
Renvoieinteger: la valeur totale la plus élevée qui tient dans le sac, arrondie à l’entier inférieur

Contraintes

1 ≤ n ≤ 5000, où n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Exemples

Entrée: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Sortie: 151
Explication: Par unité de poids, les objets valent 5, 3, 6 et 2.5. Les objets 2 et 0 sont pris en entier pour une valeur de 70, avec une capacité restante de 27 ; 27 des 30 unités de l’objet 1 ajoutent 81, soit un total de 151.

Entrée: values = [10, 7]weights = [4, 3]capacity = 5
Sortie: 12
Explication: L’objet 0 vaut 2,5 par unité et l’objet 1 environ 2,33, donc l’objet 0 est pris en entier pour 10. Une des 3 unités de l’objet 1 ajoute 7 / 3, et 12 et un tiers est arrondi à 12.

Pour aller plus loin

Peux-tu trouver la réponse en O(n) sans trier tous les éléments ?

Indices

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

0 sur 3 ouverts

Solution

Comme tu peux fractionner les objets, le problème est glouton, contrairement au problème du sac à dos 0/1 : chaque unité de poids doit provenir de l’objet ayant la plus grande valeur par unité restante. Trie les objets selon cette densité et remplis le sac dans cet ordre. Compare les densités par produit croisé et arrondis à l’entier inférieur uniquement la quantité de l’objet que tu fractionnes, afin qu’aucune fraction ne soit jamais stockée.

Choisissez l’élément le plus dense à chaque tour

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Remplis le sac en commençant par l’objet le plus dense : prends-le en entier s’il tient, sinon prends la quantité qui remplit le sac et arrête-toi. Trouve l’objet inutilisé le plus dense en les parcourant tous et en comparant values[i] × weights[j] à values[j] × weights[i] au lieu de diviser. Avec des poids positifs, le test est équivalent et les deux produits restent inférieurs ou égaux à 10^8.

Commencer par le plus dense est optimal : si le sac contient une certaine quantité d’un objet moins dense alors qu’un objet plus dense n’y est pas entièrement, remplacer cette quantité par l’objet plus dense ne peut pas réduire la valeur. En répétant ces échanges, on obtient le chargement qui commence par les objets les plus denses.

Jusqu’à n tours parcourent chacun les objets inutilisés, soit environ n²/2 = 12.5 millions de comparaisons pour n = 5000.

Algorithme

Marque chaque élément comme inutilisé et définissez room = capacity et total = 0.
Tant qu’il reste de la place, parcourez les éléments inutilisés pour trouver celui dont la densité est la plus élevée, en comparant les densités par multiplication croisée.
S’il ne reste aucun élément, arrêtez-vous. Sinon, marquez cet élément comme utilisé.
S’il tient, ajoutez sa valeur à total et déduisez son poids de room. Sinon, ajoutez values[i] × room / weights[i] avec une division entière, puis arrêtez-vous.
Renvoyez total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Trier par valeur par unité de poids

Intuition

Le parcours trouve encore et encore l’élément le plus dense, mais l’ordre ne change jamais d’un tour à l’autre. Trie les éléments une seule fois, du plus dense au moins dense, avec la même comparaison par produits croisés. Les éléments de même densité peuvent être placés dans n’importe quel ordre, puisqu’ils ont la même valeur par unité.

Prends les éléments entiers tant qu’ils tiennent. Le premier qui ne tient pas est le seul que tu fractionnes : il ajoute values[i] × room / weights[i], et la division entière arrondit le résultat à l’inférieur. Tout ce qui le précède est un nombre entier, donc l’arrondi de ce seul terme donne la réponse exacte. Le tri coûte O(n log n) et le parcours O(n).

Algorithme

Créez une liste des indices des objets et triez-les par densité décroissante à l’aide de la comparaison par produits croisés.
Définissez room = capacity et total = 0.
Pour chaque objet dans cet ordre, si weights[i] ≤ room, ajoutez sa valeur et déduisez son poids de room.
Sinon, ajoutez values[i] × room / weights[i] avec une division entière, puis arrêtez-vous.
Retournez total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Pièges et cas limites

Trier uniquement par valeur ou par poids. Dans le premier exemple, l’objet valant 90 n’arrive qu’en troisième position selon sa densité ; le prendre en premier laisse de la place pour la moitié de l’objet valant 50, soit 115 au lieu de 151.
Diviser avant de multiplier. Avec une valeur de 13, un poids de 7 et une capacité restante de 3, 13 / 7 * 3 en arithmétique entière donne 3, tandis que 13 * 3 / 7 donne le bon résultat : 5.
S’attendre à ce qu’un objet soit fractionné à chaque fois. Dans le troisième exemple, tous les objets tiennent, et la réponse est la somme de toutes les valeurs, soit 13.

Questions fréquentes3

Quelle est la complexité temporelle du problème du sac à dos fractionnaire ?

Trier les éléments par valeur par poids coûte O(n log n) et le remplissage se fait en un seul passage, donc le coût total est de O(n log n) avec un espace de O(n) pour l’ordre. Rechercher l’élément le plus dense à chaque tour coûte O(n²).

Pourquoi l’approche gloutonne fonctionne-t-elle pour le problème du sac à dos fractionnaire, mais pas pour le problème du sac à dos 0/1 ?

Le fractionnement te permet d’échanger le poids d’un objet moins dense contre celui d’un objet plus dense. Sans fractionnement, un objet dense peut laisser un espace que rien d’autre ne peut remplir. Avec des valeurs de 8, 11, 15, des poids de 2, 3, 4 et une capacité de 7, la stratégie qui choisit d’abord l’objet le plus dense prend les poids 2 et 4 pour une valeur de 23, tandis que les poids 3 et 4 donnent 26. La version 0/1 nécessite une programmation dynamique.

Comment résoudre le problème du sac à dos fractionnaire sans nombres à virgule flottante ?

Avec des poids positifs, a / b > c / d revient au même test que a × d > c × b, donc comparez les densités par produit en croix. La meilleure valeur est un nombre entier plus une fraction, values[i] × room / weights[i] pour l’objet fractionné ; une division entière donne donc exactement la réponse arrondie à l’entier inférieur.

def fractionalKnapsack(values, weights, capacity):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Résultat attendu