La conception d'un algorithme: pouvez-vous fournir une solution aux multiples problème de sac-à-dos?

Je suis à la recherche d'un code pseudo-solution à ce qui est effectivement le Plusieurs Problème De Sac-À-Dos (optimisation de la déclaration est à mi-chemin en bas de la page). Je pense ce problème est NP Complet, donc la solution n'a pas besoin d'être optimale, plutôt, si elle est assez efficace et facilement mises en œuvre et qui serait la bonne.

Le problème est: est-ce

  • J'ai de nombreux éléments de travail, et chacun prend un autre (mais fixe et connu) montant de temps pour terminer.
  • J'ai besoin de diviser ces éléments de travail en groupes, de façon à avoir le plus petit nombre de groupes (dans l'idéal), chaque groupe de postes de travail en prenant pas plus d'un total de seuil - dire 1 heure.

Je suis flexible sur le seuil, il ne faut pas être appliqué de manière rigide, mais devrait être proche. Mon idée était de répartir les éléments de travail dans des bacs où chaque cellule représente 90% du seuil de 80%, 70% et ainsi de suite. Je pourrait alors correspondre à des éléments qui prennent 90% de ceux qui prennent 10%, et ainsi de suite.

Toutes les meilleures idées?

Avez-vous essayez de lire le fichier PDF à partir de la page de Wikipédia? diku.dk/hjemmesider/ansatte/pisinger/95-1.pdf (PDF)
ouais j'ai fait, j'ai du mal à donner un sens à des déclarations comme 1w e - e ð ðñ | y e ðñ ò ñ e ð ó
ok, ça ne fonctionne pas, mais vous voyez l'idée

OriginalL'auteur MalcomTucker | 2010-03-06

  1. 8

    Vous avez besoin http://www.or.deis.unibo.it/knapsack.html, chapitre 6.6 "Plusieurs knapscack problème Approximative des algorithmes". Il est de la pseudo-code (Pascal style) dans le texte et Fortran implémentations (oui, c'est un vieux livre) dans un fichier ZIP.

    +1 je vous remercie beaucoup pour le lien BTW deux Martello et Toth ont été mes professeurs à l'Uni!!!

    OriginalL'auteur AVB

  2. 2

    Autant que je sache, le problème est NP complet (Wikipedia confirme), donc il n'y a probablement pas beaucoup de sens pour tenter de le résoudre exactement.
    Cependant, un certain nombre d'approches pourrait être assez bon pour vous: gourmand, algorithmes génétiques, simuler recuit...gourmand est probablement le plus simple à mettre en œuvre:

    while (time available in block greater than smallest task duration)
  find the longest fitting task
  add it

    ...vous voyez l'idée.

    J'ai le problème suivant - math.stackexchange.com/questions/2415617. Existe-il des gourmands approches pour qui?

    OriginalL'auteur Tomislav Nakic-Alfirevic