Problème de sacs à dos avec des contraintes sur les valeurs de l'article

Question

donné $ n $ articles avec poids $ w_1, ..., w_n $ et valeurs < span class="math-conteneur"> $ v_1, ..., v_n $ et une limite de poids $ w $ , le but est toujours de maximiser la valeur totale des éléments à transporter (sans dépasser la limite de poids). Maintenant, une nouvelle contrainte est, une fois qu'un élément de valeur $ v_i $ est pris, tous les éléments dont la valeur est supérieure à $ v_i $ doit également être pris. (Il est correct de supposer que tout $ v_i $ est différent)

Mon objectif est d'atteindre cet objectif dans $ o (n) $ temps, et voici ma tentative (supposons que l'entrée est une matrice $ A $ de tuples $ (w_i, v_i) $ ):

1. Calculer le poids total des éléments: $ w _ {\ mathrm {total}} \ obtient \ sum_ {i= 1} ^ n w_i $ ;

2. tandis que $ (w _ {\ mathrm {total}}}> w) $ faire:

   2.1 $ p \ obtient $ médiane des valeurs dans $ A $

   ;
   ;

   2.2 $ R \ obtient $ éléments dont la valeur est supérieure à $ p $ ;

   2.3 $ l \ obtient un \ setminus r $ ; (éléments dont la valeur est plus petite que $ p $ )

   2.4 $ w_r \ obtient $ $ $ \ sum_ {A [i] \ in r} w_i $ ;

   2.5 $ w _ {\ mathrm {total}} \ obtient w_r $ ;

   2.6 $ a \ obtient r $ ;

3. $ w \ obtient w- w _ {\ mathrm {total}} $ ; (la capacité restante)

4. répéter l'étape 2 pour le tableau $ l $ , générant la matrice $ l '$ ;

5. retour $ l '\ tasse a $ ;

Notez que l'algorithme de recherche des coûts médians temps linéaire.

Je présume que mon algorithme coûte $ o (n) $ temps car, pour chaque itération dans chaque boucle de chaque boucle, la taille de l'entrée est de moitié - mais je ne suis pas 100% confiant de cela. Cet algorithme coûte-t-il donc vraiment un temps linéaire? Sinon, quelles amendements peuvent être apportés ou y a-t-il une idée générale de concevoir un tel algorithme qui coûte du temps linéaire? Toute aide sera très appréciée! :)

Answer 1

Oui, votre algorithme fonctionne dans $ O (n) $ Si vous utilisez l'algorithme médian des médianes. Vous pouvez prouver que vous en consultez votre algorithme et en notant que dans toutes les boucles, la taille de la matrice que nous considérons est coupée en deux. Et le temps d'exécution du corps de boucle est $ o (n) $ (si nous utilisons la médiane des médianes et la copie de la matrice / filtrage est $ O (n) $ quand même). Maintenant, nous obtenons la somme suivante:

$$ \ sum_ {i= 0} ^ {\ journal (n)} \ frac {n} {2 ^ i} \ Leq \ sum_ {i= 0} ^ {\ \ \fty} \ frac {n} {2 ^ i}= n \ CDOT \ SUM_ {i= 0} ^ {\ \} \ frac {1} {2 ^ i}= 2n \ in o (n) $$

la $ \ journal (n) $ provient du fait que vous ne pouvez diviser que la taille de la matrice $ log ( n) $ fois en moitiés jusqu'à ce que vous arriviez à $ 1 $ (car $ 2 ^ {\ log (n) }= n $ ). Chaque terme de la somme exprime le coût d'une exécution du corps de la boucle.