Est cette variante du sous-ensemble somme problème plus facile à résoudre?
j'ai un problème lié au problème de la somme des sous-ensembles et je me demande si les différences le rendent plus facile, c.-à-d. soluble dans un délai raisonnable.
étant donné une valeur V, une taille l définie et une séquence de nombres [1, N] S, combien de sous-ensembles de taille L de s sont inférieurs à V?
c'est différent du problème de la somme du sous-ensemble de trois façons:
- je vous préoccuper du nombre de sous-ensembles sont moins qu'une valeur donnée, pas combien sont égal .
- les tailles des sous-ensembles sont fixes.
- I care combien jeux à somme à moins de V, pas seulement si il existe.
Existe-t-il un algorithme raisonnablement efficace pour résoudre ce problème?
Edit: Évidemment, cela peut être fait en O (N choisir L) en utilisant une combinaison générant algorithme. Ce qui m'intéresse, c'est des piratages astucieux pour accélérer les choses.
9 réponses
(la version de décision de) votre problème est toujours NP-complet. L'idée est que si nous pouvions résoudre votre problème, alors (pour chaque taille de sous-ensemble, disons) nous pourrions demander combien d'ensembles somme à moins que V et combien somme à moins que V-1, et la différence de ces deux nombres nous diraient si sont des sous-ensembles que la somme à exactement V -- ainsi nous pourrions résoudre le problème de somme de sous-ensemble. [Ceci n'est pas une preuve complète, parce que c'est un réduction de Turing , pas un beaucoup réduction .]
cependant, il y a une solution simple programmation dynamique qui court dans le temps O(nLV). [La raison pour laquelle cela ne prouve pas que P=NP est que V pourrait être exponentielle dans la taille d'entrée: avec n bits, vous pouvez représenter des valeurs jusqu'à 2 n . Mais en supposant que votre V n'est pas exponentielle, ce n'est pas un problème.]
soit num[v] [k] [i] indique le nombre de sous-ensembles de taille k du premier i vous pouvez les calculer comme (pour chaque i):
num[0][0][i] = 1
for v = 1 to V:
for k = 1 to L:
num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]
où S[i] est le ième élément de votre séquence. (N'importe quel ensemble de la taille k qui additionne à v soit n'utilise pas S[i], donc il est compté dans num[v][k][i-1], ou il utilise S[i] ce qui signifie que le reste du sous-ensemble a des éléments k-1, utilise seulement les premiers numéros i-1 dans la séquence, et les sommes à v-S[I].) Enfin, Compter num[v][L] [|S|] pour chaque v inférieur à V; c'est votre réponse.
En outre, vous pouvez omettre le troisième indice si vous le faites soigneusement (exécuter votre boucle vers le bas pour chaque i, etc.); Je n'inclus pour plus de clarté.
Je ne suis pas prêt à présenter une preuve, mais cela sonne comme il pourrait se prêter à un schéma de programmation dynamique: tabuler la liste des sous-ensembles de taille 2 les utiliser à des sous-ensembles informatiques de taille 3, etc, de sorte que hyou n'a besoin d'examiner une petite collection de perspectives.
une optimisation qui vient à l'esprit est celle-ci: ordonnez votre séquence (si ce n'est déjà pas le cas). Choisissez la première L-1 éléments de la démarrer, puis sélectionnez le dernier élément, par exemple, que c'est la plus grande valeur possible (la deuxième plus grande valeur dans la séquence donnerait une somme trop importante). Jeter le reste de la séquence, parce que ces éléments ne peuvent jamais être une partie d'un sous-ensemble valide de toute façon.
après ça, je suppose que c'est encore une recherche complète. Mais là encore, il y a peut être d'autres optimizations possible too.
N'est-ce pas juste le problème de sac-à-Dos avec un twist? Peut-être que j'ai mal.
la solution de programmation dynamique au problème de la somme des sous-ensembles génère une table qui contient cette réponse (i.e. une table booléenne de V par N Où V est le nombre maximum d'éléments et N est le nombre maximum d'éléments qui peuvent être dans un ensemble qui satisfait les contraintes; chaque booléen étant vrai si <=n la somme des éléments à <=V). Donc si N * V n'est pas trop grand pour vous, un algorithme assez rapide existe. La solution de somme de sous-ensemble est juste l'élément de série le plus élevé dans ce tableau pour lequel le nombre de les éléments <= N/2.
si c'est seulement des entiers positifs, vous pouvez faire une étape de vérification si vous avez besoin de ;
prend la somme des plus petits entiers de L-1 dans l'ensemble. Si c'est une somme X, alors n-X doit être sous le plus grand élément si le problème est supposé pour avoir une solution. En y repensant, vous pouvez éliminer l'autre L de cette façon...
Eh bien, pour une chose puisque vous spécifiez Taille=L alors même si vous ne pouvez pas penser à quelque chose d'intelligent et juste utiliser la force brute, vous aurez (n choisir L) des sommes séparées dans le pire des cas, donc c'est un peu mieux que n^^l (Bien, L+1, comme vous feriez alors la somme de chaque sous-ensemble).
cela ressemble à un n choisir K catégorie de problème. La génération des sous-ensembles k de n est traitée dans le manuel de conception de L'algorithme de Skiena, et le livre suggère d'énumérer les sous-ensembles pertinents dans l'ordre lexicographique (récursivement, par exemple). Ensuite, faites votre somme et de comparaison sur chaque sous-ensemble.
si vous avez un ensemble trié, vous pourriez probablement tailler les solutions impossibles de l'espace de solution.
peut-être la formulation de programmation dynamique est amenamble à un PTAS de FPTAS.