Algorithme d'optimisation de la distribution

Question

J'essaie de classer et de trouver une solution raisonnable pour le problème suivant (résumé d'un problème réel du monde).

problème

Imagine Stackoverflow a commencé à offrir un abonnement où les entreprises pouvaient acheter x nombre d'impressions par mois pour un ensemble de balises.

Par exemple, vous pourriez être intéressé à exécuter une annonce avec 50000 impressions sur les balises suivantes: javascipt, typescript, react, nextjs, nodejs, webpack.

Stackoverflow "Promises" Vous obtiendrez 50000 impressions, mais ils sont libres de les distribuer sur les balises ci-dessus, mais ils désirent (pouvaient même être 100% à une étiquette).

Comment Stackoverflow optimiser la distribution de manière à pouvoir vendre / livrer le nombre maximum d'impressions?

Pour la simplicité, supposez:

• Nous connaissons le nombre d'impressions chaque étiquette reçoit par mois à l'avance et cela ne change pas
• Chaque impressions n'appartient qu'à une seule étiquette

ma recherche

Je crois que cela pourrait être similaire au Knapsack ou Bin Emballage Problèmes.

Le moyen le plus simple d'approcher est avec un "premier ajustement" (ou peut-être mieux décrit comme "premier arrivé, premier serveur") algorithme:

1. Obtenez tous les "abonnements" actifs (impressions et balises), commandé par la date de création ASC
2. Pour chaque "abonnement", saisissez la première étiquette et "consommez" autant d'impressions que possible. Si l'abonnement a toujours des impressions restantes, passez à la balise suivante.
3. Répétez avec l'abonnement suivant

qui pourrait jouer quelque chose comme ceci:

==Inventory==

Tag          Impressions
javascipt    2000
typescript   5000
react        5000
nextjs       5000


== Subscriptions ==

Acme:  8000  (javacript, typescript, react, nextjs)
Stark: 5000  (javacript, typescript)

== Allocation Results ==

Acme: 
 - javacript:  2000
 - typescript: 5000
 - react:      1000

Stark: 
 - javacript:  0
 - typescript: 0

L'optimisation de cette solution est clairement horrible. Dans l'exemple ci-dessus, alors que nous avions plus que suffisamment d'impressions pour faire le tour, nous avons alloué les seuls auxquels "Stark" pourrait acheter avant d'y arriver.

Y a-t-il un nom officiel à ce problème et que ressemble la solution optimale?

Answer 1

Je pense que c'est en fait "juste" la correspondance de bipartite de cardinalité maximale, qui peut être résolue de manière optimale dans $ o (| e | \ sqrt {| v |}) $ Temps en utilisant le Algorithme Hopcroft-Karp .

D'un côté, vous avez un sommet pour chaque impression demandée (par exemple, un client A demande 50000 de "JavaScript" ou "TypeScript", et le client B demande 10000 "JavaScript", donc 60000 sommets de tous) et sur L'autre côté, vous avez un sommet pour chaque impression fournie (disons, 30000 étiquetés "JavaScript" et 15000 étiquetés "TypeScript", donc 45000 sommets de tous). Dessinez un bord de chacune impression demandée à toutes les impressions fournies d'un type qui satisfait à ses contraintes de type impression (il y aurait donc 45 000 bords laissant chacun des sommets de client A et 15 000 bords laissant chacun des clients B) et résolvent.

Si vous avez des milliers d'impressions, vous pouvez vous retrouver avec des millions de bords, ce qui pourrait prendre trop de temps. Si une réponse approximative suffit, je suggérerais de diviser tous les chiffres par certains constants, par exemple. 1000, puis les multiplier ensuite ensuite ensuite. (Si cette constante divise tous les numéros d'entrée, la solution restera optimale.)

Answer 2

Si vous n'aviez qu'une seule étiquette, cela deviendrait un problème de sacs à dos: en particulier, déterminer si vous pouviez vendre toutes les impressions serait exactement le problème du sous-ensemble.Par conséquent, le problème est le NP-dur.

Une approche plausible pour la résoudre en pratique serait d'utiliser une programmation linéaire entière.