Diferencia entre revisiones de «Problema de la suma de subconjuntos»
Contenido eliminado Contenido añadido
m robot Añadido: fr:Problème de la somme de sous-ensembles |
m Correcciones menores, (WP:CEM) |
||
Línea 36:
y queremos encontrar un subconjunto cuya suma sea 0. Representemos ´la suma de valores negativos con ''N'' y la suma de valores positivos con ''P''. Definamos la función booleana
:''Q''(''i'', ''s'')
como ('''verdadera''' o '''falsa''') de
Línea 46:
Es claro que
:''Q''(''i'', ''s'') = '''falso'''
si ''s''<''N'' o ''s''>''P''.
Crear un arreglo para guardar los valores de ''Q(i, s)'' para ''1≤i≤n'' y ''N≤s≤P''. El arreglo puede ser llenado con una recursión simple.
:''Q(1,s)'' = "''s''=0 '''or''' ''x<sub>1</sub>=s''".
Línea 56:
Para ''i''>1,
:''Q(i, s)'' = ''Q(i-1,s)'' '''o''' ''Q(i-1,s-x<sub>i</sub>)''.
El número total de operaciones aritméticas es
Línea 79:
* '''si''', cuando existe un subconjunto que sume ''s'';
* '''no''', si no existe un subconjunto que sume algún total entre ''(1-c)s'' y ''s'' para
* cualquier respuesta, si algún subconjunto suma algún total entre ''(1-c)s'' y ''s'' pero ninguno suma ''s''.
| |||