Je pense que cela pourrait être une variation du problème de sac à dos multiple (ou peut-être même pourrait être réduit à cela) mais je ne suis pas sûr. Voici le problème:Variation sur l'algorithme du sac à dos
Vous avez un ensemble d'éléments avec des valeurs et des poids connus. Vous avez également un ensemble de sacs à dos, et chaque sac à dos peut contenir un nombre fixe d'objets (différents sacs à dos peuvent contenir différents nombres d'objets). Maximiser la valeur totale des articles dans les sacs à dos tout en restant sous un poids donné.
Notez que les sacs à dos individuels n'ont pas de restriction de poids. Chaque sac a seulement une restriction "nombre d'éléments qu'il peut contenir". La seule autre restriction est le poids total des articles.
Des idées? (autre que la force brute bien sûr). Merci d'avance! :)
EDIT: une restriction importante que j'oublié d'inclure:
articles ne peuvent pas nécessairement être mis dans un sac. Essentiellement, leur valeur devient nulle si elles sont mises dans un sac avec lequel elles ne sont pas compatibles. Vous pouvez imaginer un cas général où chaque objet a une valeur dépendant de son sac, mais pour mon cas, sa valeur sera soit 0, soit sa valeur normale, selon le sac.
Est-ce que ce travail est fait? Si oui, nous devrions marquer est comme tel. Qu'avez-vous essayé? –
Euh - devoirs? :) Je vais probablement avoir de la haine ici. – SinisterRainbow
Ceci est "Knapsack" si vous traitez tous les différents Knapsacks comme un seul Knapsack c'est pareil. Il y a plusieurs façons d'approcher Knapsack. Je suis sûr que vous pouvez les trouver si vous faites une recherche google. – twain249