J'aimerais savoir s'il y a un algorithme plus optimal pour le cas ci-dessous que de simples itérations sur la collection d'articles.
Supposons qu'il y ait plusieurs éléments (2-10) avec du poids défini comme une plage et une augmentation, comme
Item1 [0, 50] Incrément = 5
Item2 [40, 60] incrément = 10.
La tâche consiste à vérifier s'il y a au moins une combinaison de poids qui s'étend jusqu'à 100. Dans l'exemple ci-dessus, il y a 50 + 50 et 40 + 60 combinaisons.
Comme le nombre d'articles n'est pas grand, il ne faut pas prendre beaucoup de temps sur tous les objets, mais peut-être qu'il y a une meilleure façon.
merci
mise à jour: je cherche un algorithme qui ne nécessite pas la liste de tous les poids ou poids possibles, j'ai besoin d'un algorithme qui vérifie s'il y a au moins une combinaison de poids équivaut à 100 connaître la plage et l'incrémentation
4 Réponses :
Vous pouvez créer un ensemble de tous les poids possibles que vous pouvez produire. Les poids au-dessus du total sont supprimés.
def weight_sum(items, total):
possible = set([0])
for weight_range, increment in items:
new_possible = set(possible)
for w in xrange(weight_range[0], weight_range[1] + 1, increment):
new_possible.update(p + w for p in possible if p + w <= total)
possible = new_possible
return total in possible
items = [[[0, 50], 5], [[40, 60], 10]]
print weight_sum(items, 100)
-> True
print weight_sum(items, 111)
-> False
force brute en python (je suppose que chaque somme doit contenir des poids de tous les éléments): où produit () est un produit cartésien:
Ce problème semble être une version du Sous-Sum Problème , qui est NP-complet. Par conséquent, la réponse est non, il n'y a probablement pas un algorithme efficace dans le cas général. Quelques
Fait intéressant, je crois que le problème du sous-ensemble classique sur l'un de ces ensembles {X, X + N, X + 2N, ..., y} est au plus O (t) pour une somme cible T. (peut-être encore moins, Mais je ne pouvais pas faire mieux.)
Si je comprends ce droit, nous avons donné un total T (avec t = 100 dans ce cas) et K paires de gammes et d'intervalles
([x 1 , y 1 ], n 1 ), ([x 2 , y 2 ], n 2 ), ... ([x et pour chacun d'eux, nous devons choisir une valeur
a i ∈ {x i , x i + n i , x i < / SUB> + 2N I , ..., Y I }
de sorte que
A 1 + A 2 + ... + A K = T
x 1 + C 1 n 1 + x 2 + C 2 N 2 + ... + x K + C K N K = T
Sous réserve des contraintes
0 ≤ C i ≤ (y i -x i ) / n i pour tout i.
En fait, cela appartient à un sous-ensemble de problèmes encore plus spécifique, car toutes les variables C I ne peuvent prendre qu'un nombre fini de valeurs (étant des entiers, délimités ci-dessus et ci-dessous). Certains Googling pour CLP (FD) (Programmation logique de contrainte sur les domaines finis) pourraient vous donner une idée de la manière dont elles sont approchées en général (cependant, cela peut être un cas particulier avec une solution plus facile que je ne suis pas au courant). < / p>
Fondamentalement, le problème est de trouver des valeurs C i satisfaisant
Je crois que c'est ce qu'ils appellent un problème de satisfaction de la contrainte entier linéaire . La classe générale des approches de ce type de problèmes est appelée Programmation linéaire entier . De tels problèmes sont généralement complets (bien que je ne connaisse pas assez pour commenter ce cas particulier), mais je pense qu'il y a encore des heuristiques relativement efficaces.
Simple itération? Qu'est-ce que ce simple itération? Comme je peux penser à cela, il y a une force brute ou une DP non simple itération.
En itérant simple, je veux dire création de la liste de chaque élément Poids possibles, puis résumé de ces poids un par un. Je suppose que vous voulez dire la même chose par la force brute