| Español | English |
Dado un conjunto arbitrario de enteros,¿ Existe un subconjunto cuya suma sea exactamente un valor dado ? |
|---|
En esta ocasión nos vamos a ocupar de una versión del problema enunciado, restringiendo el conjunto de partida a los enteros positivos.
Este problema puede abordarse en el contexto de las particiones de enteros, ver [suma_de_subconjuntos@j2e2xae] , pero en este caso vamos a solucionarlo en la forma de una recurrencia.
⑴
⑵
⒜
⒝
⌘
Dados un conjunto de enteros positivos S = { a1 , a2 , ... am } y un entero positivo k,
Definimos una función F , con valor el número de subconjuntos de S con suma k .
Si quitamos el elemento nm , el subconjunto resultante da lugar a dos opciones para la realización de la suma, puedes elegir entre k y k − nm </sub.
Hemos determinado una relación de recurrencia que nos permite resolver el problema de dimensión ( m, k ) con las soluciones en ( m − 1, k − n m ) y ( m − 1, k ).
Teniendo en cuenta las igualdades siguientes,
Podemos construir una solución recursiva ⒜ , ⒝
con casos base, ecuación ⒜ ,( ∅ , k ) y ( S , 0 ),
que ha de conservar las propiedades ⑴ y ⑵ .
Ordenar los elementos del conjunto de forma ascendente facilita la tarea de verificar las propiedades.
∎
| English | Español |
An integer set given,Is there any subset that sums precisely upto other integer ? |
|---|
We restrict our attention to a variant of this problem involving positive integers only.
This problem could be solved as an integer partitions one, see [subset_sum@j2e2xae], now we are solving it by a recurrence relation.
⑴
⑵
⒜
⒝
⌘
Given a positive integer set S = { a1 , a2 , ... am } and a positive integer k,
A function defined F , with value the number of S subsets that sum upto k .
Drop nm , remaining subset has two options to sum, k or ( k − nm ),
That is a recurrence relation that solves the problem ( m, k ) using solutions ( m − 1, k − n m ) and ( m − 1, k ).
Note the equalities,
We can build a recursive solution ⒜ and ⒝,
with base cases, ( ∅ , k ) and ( S , 0 ), in equation ⒜
and an invariant as properties ⑴ and ⑵ .
Ascendig ordering makes verifying invariant properties easier.
∎
Media
