Comment résoudre un sac à dos fractionnaire en temps linéaire? Jai trouvé ceci sur Google mais je ne le comprends pas vraiment.
- Choisissez lélément $ r $ au hasard parmi $ R $ (ensemble de ratios bénéfice / poids)
- Déterminer
- $ R_1 = \ {p_i / w_i | p_i / w_i > r, pour 1 \ leq i \ leq n \}, W_1 = \ sum_ {i \ in R_1} w_i $
- $ R_2 = \ {p_i / w_i | p_i / w_i = r, pour 1 \ leq i \ leq n \}, W_2 = \ sum_ {i \ in R_3} w_i $
- $ R_3 = \ {p_i / w_i | p_i / w_i < r, pour 1 \ leq i \ leq n \}, W_3 = \ sum_ {i \ in R_3} w_i $
- if $ W_1 > W $
- recurse $ R_1 $ et renvoyer la solution calculée
- else
- while (il y a de lespace dans le sac à dos et $ R_2 $ nest pas vide)
- ajouter des articles à partir de $ R_2 $
- si (le sac à dos est plein)
- renvoyer les articles en $ R_1 $ et les articles qui viennent dêtre ajoutés à partir de $ R_2 $
- else
- réduisent la capacité du sac à dos de W_1 $ + W_2 $
- récurent sur $ R_3 $ et renvoyer les articles dans $ R_1 \ cu p R_2 $
- ajouter des éléments renvoyés par un appel récursif
- while (il y a de lespace dans le sac à dos et $ R_2 $ nest pas vide)
Je ne comprends pas comment fonctionne, ce que $ R $ et $ W $ sont censés représenter … quelquun peut-il expliquer? Ou peut-être si vous avez un autre algorithme à proposer?
Réponse
Ce serait bien si vous posiez le problème. Je suppose que vous avez $ n $ éléments $ x_i $ , chacun ayant un profit $ p_i $ et poids $ w_i $ . Vous voulez maximiser votre profit sous la contrainte que le poids total est au plus $ W $ . Pour chaque élément $ x_i $ , vous êtes autorisé à mettre nimporte quelle fraction $ \ theta \ dans [0,1] $ de celui-ci, ce qui vous rapportera un profit $ \ theta p_i $ et un poids $ \ theta w_i $ .
Voici un exemple. Vous avez de lor brut, avec un profit de 1 000 $ et un poids de 1 $ . Vous avez aussi des bananes, avec un bénéfice de 1 $ et un poids 10 $ . Supposons que vous puissiez porter un poids de 2 $ $ . Quest-ce que tu ferais? Naturellement, vous mettriez dabord autant dor que vous le pouvez – à savoir, tout cela, puis vous mettriez autant de bananes que vous le pouvez – à savoir, un dixième, pour un profit total de 1000.1 $ .
Lalgorithme général est similaire. Supposons que vous divisiez $ W $ en un 1 000 $ $ « slots », que vous voulez remplir avec le plus article-parties de poids rentables $ W / 1 000 $ . Pour un article pesant $ w_i $ , nous avons $ w_i / (W / 1000) $ pièces (supposons pour le moment quil sagit dun entier), et chacun deux vaut $ p_i / (w_i / (W / 1000)) $ . Au moment de choisir quoi mettre dans un emplacement, nous aimerions maximiser notre profit, et donc nous choisissons lélément avec un maximum $ p_i / w_i $ , et le mettons autant pièces que possible. Si nous manquons, nous choisissons lélément avec le prochain plus grand $ p_i / w_i $ , et ainsi de suite.
Vous pouvez implémenter cela sans diviser $ W $ dans un $ 1000 $ pièces: choisissez lélément avec un $ p_i / w_i $ , et mettez-en autant que possible. Si vous êtes à court, choisissez le suivant et mettez-en autant que possible. Etc. La mise en œuvre de cet algorithme nécessite le tri de la liste $ p_i / w_i $ , ce qui prend du temps $ O (n \ log n) $ . Lalgorithme que vous décrivez utilise la même astuce que dans quickselect pour réduire le temps dexécution à $ O (n) $ , au prix de rendre lalgorithme aléatoire.
Je suggère la voie suivante pour comprendre lalgorithme:
- Comprendre lalgorithme glouton classique pour le sac à dos fractionnaire.
- Comprendre la sélection rapide.
- Voyez comment lalgorithme que vous citez combine la technique de sélection rapide avec lapproche gourmande.
Réponse
R est le ensemble de ratios profit / poids de chaque objet , où le profit et le poids des objets sont donnés. Et W est la Capacité du sac à dos .
Maintenant, au lieu de choisir un élément aléatoire en 1 étape, nous pouvons appliquer algorithme de recherche médiane à trouver la médiane en O (n) fois.
Et puis nous pouvons faire le reste de toutes les étapes.Lanalyse de la complexité du temps sera donc –
T (n) = T (n / 2) + O (n).
Et nous obtiendrons O (n) comme solution. Dites-moi si quelque chose nest pas correctement expliqué et que vous voulez en savoir plus.
Réponse
En temps linéaire, vous pouvez trouver le article médian en termes de valeur par unité de poids. Ensuite, également en temps linéaire, vous pouvez déterminer si vous pouvez placer tous les articles qui sont au moins aussi précieux dans le sac à dos ou non. Si vous le pouvez, faites-le et résolvez récursivement ce problème pour les éléments n / 2 de valeur inférieure étant donné que vous » vous avez déjà rempli le sac à dos. Si vous ne pouvez pas « t, vous pouvez jeter les n / 2 articles de valeur inférieure, puis essayez à nouveau de résoudre le problème avec uniquement les éléments n / 2 de valeur la plus élevée.
La récurrence ici est T (n) = T (n / 2) + O (n) , et nous avons cela T (n) = O (n) , comme vous le souhaitez.
Dans la solution que vous avez collée: R est lensemble des ratios, bénéfice / poids W est la somme du poids total de cet ensemble , utilisé pour comparer avec la capacité de votre sac à dos. De même, {pi / wi | pi / wi} représente le ième élément que le profit est à la ième valeur de poids. Nous comparons cette valeur à la valeur sélectionnée au hasard r , puis nous la séparons en fonction de la comparaison du rapport. Les R1, R2, R3 sont dautres sous-ensembles du rapport défini selon que le rapport est inférieur, égal ou supérieur à celui de lélément médian.
de même, les W1, W2, W3 sont la somme des poids de ces ensembles.
Choisissez maintenant le jeu de solutions approprié en fonction des valeurs de rapport comme expliqué au début.