-1
Supposons que je possède un magasin & seulement vendre des articles dans des groupes de deux.Comment résoudre (ou nommer) cet algorithme ressemblant à un knapsack
- Si je vends un CRAYON et un effaceur, je gagne 3
- $ Si je vends un CRAYON et un MARBRE, je gagne 2
- $ Si je vends un RULER et un effaceur, je gagne 2 $
Chaque client est prêt à acheter jusqu'à 1 article de chaque & Je veux maximiser le profit. Par conséquent, vendre # 1 et # 2 est illégal parce que ce serait 2 crayons. # 1 et # 3 serait également illégal en raison des gommes. Ainsi, les mouvements légaux sont: seulement # 1, seulement # 2, seulement # 3, ou # 2 et # 3. Puisque la dernière option a un bénéfice de 5 $, je devrais le faire. Comment pourrais-je résoudre ce problème en temps polynomial? Si c'est np-hard, quelle heuristique pourrait me rapprocher? Si rien d'autre, ce problème a un nom?
Qu'avez-vous essayé? Nous sommes prêts à vous aider avec vos devoirs, mais vous devez montrer un effort :) – Parker
Ma seule pensée est une boucle imbriquée (pour chaque groupe qui comprend un crayon, pour chaque groupe qui implique une règle ....) mais que pousse assez rapidement. Pas de soucis de me tromper d'apprentissage, c'est en fait quelque chose que je construis sur un algo hongrois pour un problème de routage de véhicules. –
Quelles sont les restrictions? Il semble que je devrais toujours vendre 2 & 3 à chaque client, je ne comprends peut-être pas la question complètement – Parker