variation intéressante au problème de la somme sous-ensemble

Question

Une variante intéressante du problème de la somme sous-ensemble m'a été présenté par un ami du travail:

Étant donné un ensemble S d'entiers positifs, de taille n, et des nombres entiers a et K, existe-t-il un sous-ensemble R (de l'ensemble S) qui contient exactement les éléments, dont la somme est égale à K? Il prétend que cela peut être fait avec la complexité du temps O (nka), je n'ai pas pu trouver un algorithme de programmation dynamique qui a atteint ce temps de fonctionnement. Peut-il être fait?

Answer 1

Il peut se faire que si k et sont assez petits, afin que nous puissions déclarer un tableau

bool found[a][k] 

Vous serait itérer sur chaque valeur dans S et itérer sur tous les états dans le trouvé tableau à obtenir un nouvel état.

Say, pour les indices a = 1 et k = 7, et la valeur actuelle de S étant 7,

se trouve [1] [7] est vrai, alors vous pouvez être sûr que trouvé [2] [14] est également vrai.

Lorsque l'itération se termine, tout ce que vous devez faire est de vérifier que [a] [k] est vrai ou non.

Answer 2

Soit S = {s1, \ ldots, sn}

Soit P (j, K, a) est vrai ssi il est possible de trouver un éléments dans s1, \ ldots, sj qui résument à K Alors P (j, K, a) = P (j-1, K-sj, a-1) OU P (j, K, a) (soit sj soit nécessaire ou inutile).

L'algorithme consiste alors à remplir une table 3D de dimension n de K + 1 de a + 1. Chaque entrée prend un temps constant à remplir, d'où la complexité temporelle (et spatiale) est O (nKa)