variante de problème de sac à dos

Question

J'ai un nombre de 'nombre' (entiers non négatifs). Mon exigence est de déterminer un ensemble optimal de montants afin que la somme de la combinaison soit inférieure ou égale à une limite fixe donnée et que le total soit aussi grand que possible. Il n'y a pas de limite au nombre de montants pouvant être inclus dans l'ensemble optimal.

pour titre d'exemple: les montants sont 143,2054,546,3564,1402 et la limite est donnée 5000.

Selon ma compréhension du problème havresac a 2 attributs pour chaque élément (poids et valeur). Mais le problème énoncé ci-dessus n'a qu'un seul attribut (montant). J'espère que cela rendrait les choses plus simples? :)

Quelqu'un peut-il me s'il vous plaît aidez-moi avec l'algorithme ou le code source pour résoudre ce problème?

Answer 1

cela est encore un problème NP-dur, mais si vous voulez (ou doivent) faire quelque chose comme ça, peut-être ce sujet vous aide un peu:

find two or more numbers from a list of numbers that add up towards a given amount

où je solved it like this et NikiC l'a modifié to be faster. seule différence: il s'agissait d'obtenir le montant exact, pas "le plus près possible", mais ce ne serait que quelques petits changements de code (et vous devrez le traduire dans la langue que vous utilisez).

un coup d'oeil sur les commentaires dans mon code pour comprendre ce que je suis en train de faire, Wich est, dans sa forme courte:

• calculer toutes les combinaisons possibles des parties données et les résumé
• si le résultat est le montant que je cherche, sauver la solution à un tableau
• au moins, trier toutes les solutions possibles pour obtenir une aide de parties les moins

de sorte que vous devrez changer :

• sauver une solution si elle est inférieure à la quantité que vous cherchez
• solutions de tri par montant total au lieu de nombre de pièces utilisées

Answer 2

Le livre "Knapsack Problems" Par Hans Kellerer, Ulrich Pferschy et David Pisinger appelle cela La somme des sous-ensembles Problème et lui consacre un chapitre entier (chapitre 4). Le chapitre est très complet et couvre les algorithmes ainsi que les résultats de calcul.

Même si ce problème est un cas particulier du problème de sac à dos, il est toujours NP-difficile.