Couper des bâtons égaux de différents bâtons

Vous avez $n$ bâtons de longueurs arbitraires, pas nécessairement intégrales.

En coupant quelques bâtons (une coupe coupe un bâton, mais nous pouvons couper aussi souvent que nous le voulons), vous voulez obtenir $k<n$ bâtons tels que:

• Tous ces $k$ bâtons ont la même longueur;
• Tous les $k$ sticks sont au moins aussi longs que tous les autres sticks.

Notez que nous obtenons $n + C$ bâtons après avoir effectué des coupes $C$

Quel algorithme utiliseriez-vous pour que le nombre de coupes nécessaires soit minimal? Et quel est ce nombre?

À titre d'exemple, prenons $k=2$ et tout $n\geq 2$ . L'algorithme suivant peut être utilisé:

• Ordonner les bâtons par ordre décroissant de longueur tel que $L_1\geq L_2 \geq \ldots \geq L_n$ .
• Si $L_1\geq 2 L_2$ couper le bâton # 1 en deux morceaux égaux. Il y a maintenant deux bâtons de longueur $L_1 / 2$ , qui sont au moins aussi longtemps que les bâtonnets restants $2 \ldots n$ .
• Sinon ( $L_1 < 2 L_2$ ), coupez le bâton # 1 en deux morceaux inégaux de tailles $L_2$ et . Il y a maintenant deux bâtons de longueur , qui est plus longue que et les autres bâtons .L 2 L 1 - L 2 3 … $L_1-L_2$$L_2$$L_1-L_2$$3 \ldots n$

Dans les deux cas, une seule coupe suffit.

J'ai essayé de généraliser cela à un plus grand , mais il semble y avoir beaucoup de cas à considérer. Pouvez-vous trouver une solution élégante?$k$

La première observation fondamentale pour résoudre ce problème est que la faisabilité d'une longueur de coupe ,$l$

,$\qquad\displaystyle \operatorname{Feasible}(l) = \biggl[\, \sum_{i=1}^n \Bigl\lfloor\frac{L_i}{l} \Bigr\rfloor \geq k \,\biggr]$

est constante par morceaux, continue à gauche et non croissante en . Étant donné que le nombre de coupes nécessaires se comporte de manière similaire, trouver la longueur optimale est juste$l$

.$\qquad\displaystyle l^{\star} = \max \{ l \mid \operatorname{Feasible}(l) \}$

De plus, comme les autres réponses l'ont proposé, toutes les discontinuités de saut ont la forme . Cela nous laisse avec un problème de recherche unidimensionnel discret susceptible de recherche binaire (après avoir trié un ensemble fini de candidats).$L_i/j$

Notez en outre que nous devons seulement considérer les qui sont plus courts que le k-plus grand, car celui-ci est toujours faisable.$L_i$$k$

Ensuite, différentes bornes sur conduisent à des algorithmes d'efficacité différente.$j$

• donne un espace de recherche de taille quadratique (en k ),$1 \leq j \leq k$$k$
• dans une représentation linéaireithmique (en supposant que les L i sont triés par taille décroissante), et$1 \leq j \leq \lceil k/i \rceil$$L_i$
• limites légèrement plus impliquées dans une limite linéaire.

En utilisant cela, nous pouvons résoudre le problème proposé dans le temps et l'espace Θ ( n + k ) .$\Theta(n + k \log k)$$\Theta(n + k)$

Une autre observation est que la somme de augmente de 1 par 1 pour chaque candidat L i / j "passé", en comptant les doublons. En utilisant cela, nous pouvons utiliser la sélection de rang au lieu de la recherche binaire et obtenir un algorithme qui s'exécute dans le temps et l'espace Θ ( n ) , ce qui est optimal.$\mathrm{Feasible}$$l$$1$$L_i/j$$\Theta(n)$

Trouvez les détails dans notre article Algorithmes efficaces pour une division de bâton sans envie avec moins de coupes (par Reitzig et Wild, 2015).

Comme l'a suggéré @randomA, nous procéderons en deux phases: nous trouverons d'abord l'ensemble des bâtons qui seront coupés puis minimiserons le nombre de coupes.

Comme dans le cas particulier de la question, on trie / nomme les bâtons de sorte que . Cela prend du temps O ( n log n ) .$L_1 \ge L_2 \ge \dots \ge L_n$$O(n\log n)$

Comme l'a souligné @ user1990169, nous n'avons jamais à couper un morceau .$i\ge k$

Dans la première phase, nous utilisons une recherche binaire pour trouver le nombre , 1 ≤ s ≤ k , de sorte que les bâtons 1 , … , s peuvent être coupés en au moins$s$$1\le s \le k$$1, \dotsc, s$ morceaux de taille L s (plus quelques petits morceaux), mais les bâtonnets 1 , … , s - 1 ne peuvent pas être coupés en k morceaux de taille L s - 1 . Cela prendra du temps O ( k log k ) .$k$$L_s$$1, \dotsc, s-1$$k$$L_{s-1}$$O(k\log k)$

Si , cette valeur est la taille optimale et nous pouvons sauter la phase deux.$L_{s-1} = L_s$

Sinon, nous savons que la taille optimale satisfait L s - 1 > o ≥ L s et si o > L s alors o résulte de la coupe d'au moins un des bâtons en morceaux de taille égale. La phase deux déterminera o :$o$$L_{s-1} > o \ge L_s$$o > L_s$$o$$o$

Pour chaque bâton , 1 ≤ i ≤ s , déterminez un ensemble de tailles candidates comme suit: Si la découpe en morceaux de taille L s transforme le bâton en morceaux r i (y compris le plus court, le cas échéant), alors les candidats pour ce bâton sont toutes les valeurs L $i$$1\le i \le s$$L_s$$r_i$ , oùj≤rietL$\frac{L_i}j$$j\le r_i$. (Voirla réponse de @ user1990169pour savoir pourquoi ce sont les seules tailles candidates.)$\frac{L_i}j<L_{s-1}$

Conservez pour chaque taille de candidat, combien de fois cela s'est produit. En utilisant un arbre de recherche équilibré, cela peut être fait dans , car le nombre total de tailles candidates est lié par ∑ i r i ≤ 2 k .$O(k\log k)$$\sum_i r_i \le 2k$

Maintenant, la taille candidate qui s'est produite le plus souvent et conduit à une coupe valide est celle qui nous donne la solution optimale. En outre, si une taille candidate conduit à une coupe valide, toute taille plus petite entraînera également une coupe valide.

Nous pouvons donc à nouveau utiliser la recherche binaire pour trouver la plus grande longueur candidate qui mène à une coupe valide dans . Ensuite, nous itérons sur l'ensemble des longueurs candidates jusqu'à ce seuil et trouvons celui avec la plus grande multitude parmi eux dans O ( k ) .$O(k\log k)$$O(k)$

Au total, nous obtenons un runtime en , ou O ( k log k ) , si nous ignorons (ou n'avons pas à le faire) le tri initial.$O(n\log n)$$O(k\log k)$

Après avoir commandé les bâtons dans l'ordre décroissant de leur longueur, un bâton ne sera coupé que si tous les bâtons L $L_i$ a été coupé.$L_1, L_2, ... L_{i-1}$

Maintenant que , nous ne ferons aucune coupe sur les bâtons$k < n$ , car nous pouvons toujours avoir k bâtons de longueur L k .$L_{k}$$k$$L_{k}$

Alors maintenant, au lieu de , nous avons affaire à seulement $n$ sticks (en ajoutant éventuellement le k -th stick dans son ensemble), et le nombre maximum de coupes qui seront nécessaires dans le pire des cas = k - 1 .$k-1$$k$$= k-1$

De plus, si le nombre optimal de coupes est , alors il doit y avoir au moins un ensemble de bâtons parmi ces k - 1 bâtons qui doivent être pris dans leur ensemble à partir de 1 bâton d'origine$< k-1$$k-1$(soit en parties ou en 1 pièce) , c'est-à-dire qu'aucune partie de ce bâton d'origine ne doit être laissée «non prise». En effet, selonleprincipe dupigeonnier, il doit y avoir au moins 1 coupe qui doit produire plus d'un bâton valide.

Vous pouvez ensuite effectuer deux boucles imbriquées (les deux jusqu'à ). La boucle extérieure doit indiquer le numéro de bâton$k$ dont toutes les parties doivent être prises et la boucle intérieure doit indiquer le nombre de pièces j constituées de ce bâton. Pour chaque taille L $i$$j$
vérifiez si vous pouvez obtenir des k bâtons réalisables en coupant les bâtonsL1en séquence et si possible, mettez à jour les coupes minimales requises jusqu'à présent si le nombre actuel requis est inférieur.$\frac{L_i}{j}$$L_1$

La complexité totale de l'algorithme ci-dessus est $O(nlog(n) + k^3)$

L'idée de haut niveau serait la recherche binaire.

La taille de chacun des k bâtons demandés sera au moins le plus petit bâtonnet et au plus le plus gros. Pour cette raison, nous procédons en utilisant une recherche binaire sur la taille du bâton du milieu, voyons quel nombre nous pouvons obtenir, si ce k ' est supérieur au k donné, alors nous savons que nous devons choisir une nouvelle taille de référence candidate. Nous passons donc au plus grand ou au plus petit en utilisant un nouveau bâton de référence. On s'arrête quand k ′ est inférieur à $k'$$k'$$k$$k'$$k$

Une fois que nous avons trouvé le bâton de référence approprié, il y a un cas d'angle où nous aurions besoin d'affiner davantage la taille. Nous pouvons trier tous les bâtons coupés par le nombre de coupes sur eux et la taille du bâton. Choisissez celui avec le moins de coupes et la taille la plus petite. Réduisez le nombre de coupes sur ce bâton de 1 et faites tous les sous-bâtons de cette taille égale. Ce sera la nouvelle taille de référence, vérifiez si cette nouvelle taille peut conduire à une taille acceptable. J'avoue, je ne sais pas comment limiter le temps de course dans ce cas.$k'$

J'espère que je peux voir quelque chose d'utile à partir d'autres réponses.