| 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.
Recurrencia
⑴
⑵
⒜
⒝
⌘
Dados un conjunto de enteros positivos S = { a1 , a2 , ... am } y un entero positivo k,
∑ a > k
m
Definimos una función F , con valor el número de subconjuntos de S con suma k .
F ( n1 ,n2 ...nm ; k )
nm < k ∀ m
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 .
F ( n1 ,n2 ...nm ; k ) = F ( n1 ,n2 ...nm-1 ; k − nm ) + F ( n1 ,n2 ...nm-1 ; k )
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,
F (⋯ ; 0 ) = 0
F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )
∑ S < k ⇒ F (S ; k ) = 0
∑ S = k ⇒ F (S ; k ) = 1
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.
Ejemplo
S = { 1, 2, 3, 5, 10, 15, 20, 50 }, k = 73
∑ (1, 2, 3, 5, 10, 15, 20, 50) > 73
F (1, 2, 3, 5, 10, 15, 20, 50; 73) =
F1 (1, 2, 3, 5, 10, 15, 20; 23) +
F2 (1, 2, 3, 5, 10, 15, 20; 73)
F1 : ∑ (1, 2, 3, 5, 10, 15, 20) > 23
F1 (1, 2, 3, 5, 10, 15, 20; 23) =
F11 (1, 2, 3, 5, 10, 15; 13) +
F13 (1, 2, 3, 5, 10, 15; 23)
F11 (1, 2, 3, 5, 10, 15; 13) = F11 (1, 2, 3, 5, 10; 13)
∑ (1, 2, 3, 5, 10) > 13
F11 (1, 2, 3, 5, 10; 13) =
F21 (1, 2, 3, 5; 3) +
F23 (1, 2, 3, 5; 13)
F21 (1, 2, 3, 5; 3) = F21 (1, 2, 3; 3)
F21 (1, 2, 3; 3) = 1 + F33 (1, 2; 3)
⋮
F21 (1, 2, 3, 5; 3) = 2
F23 (1, 2, 3, 5; 13) = 0
F11 (1, 2, 3, 5, 10; 13) = 2
F13 (1, 2, 3, 5, 10, 15; 23) = 2
F1 (1, 2, 3, 5, 10, 15, 20; 23) = 4
F2 (1, 2, 3, 5, 10, 15, 20; 73) = 0
F (1, 2, 3, 5, 10, 15, 20, 50; 73) = 4 + 0 = 4
∎
| 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.
Recurrence
⑴
⑵
⒜
⒝
⌘
Given a positive integer set S = { a1 , a2 , ... am } and a positive integer k,
∑ a > k
m
A function defined F , with value the number of S subsets that sum upto k .
F ( n1 ,n2 ...nm ; k )
nm < k ∀ m
Drop nm , remaining subset has two options to sum, k or ( k − nm ),
F ( n1 ,n2 ...nm ; k ) = F ( n1 ,n2 ...nm-1 ; k − nm ) + F ( n1 ,n2 ...nm-1 ; k )
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,
F (⋯ ; 0 ) = 0
F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )
∑ S < k ⇒ F (S ; k ) = 0
∑ S = k ⇒ F (S ; k ) = 1
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.
Example
S = { 1, 2, 3, 5, 10, 15, 20, 50 }, k = 73
∑ (1, 2, 3, 5, 10, 15, 20, 50) > 73
F (1, 2, 3, 5, 10, 15, 20, 50; 73) =
F1 (1, 2, 3, 5, 10, 15, 20; 23) +
F2 (1, 2, 3, 5, 10, 15, 20; 73)
F1 : ∑ (1, 2, 3, 5, 10, 15, 20) > 23
F1 (1, 2, 3, 5, 10, 15, 20; 23) =
F11 (1, 2, 3, 5, 10, 15; 13) +
F13 (1, 2, 3, 5, 10, 15; 23)
F11 (1, 2, 3, 5, 10, 15; 13) = F11 (1, 2, 3, 5, 10; 13)
∑ (1, 2, 3, 5, 10) > 13
F11 (1, 2, 3, 5, 10; 13) =
F21 (1, 2, 3, 5; 3) +
F23 (1, 2, 3, 5; 13)
F21 (1, 2, 3, 5; 3) = F21 (1, 2, 3; 3)
F21 (1, 2, 3; 3) = 1 + F33 (1, 2; 3)
⋮
F21 (1, 2, 3, 5; 3) = 2
F23 (1, 2, 3, 5; 13) = 0
F11 (1, 2, 3, 5, 10; 13) = 2
F13 (1, 2, 3, 5, 10, 15; 23) = 2
F1 (1, 2, 3, 5, 10, 15, 20; 23) = 4
F2 (1, 2, 3, 5, 10, 15, 20; 73) = 0
F (1, 2, 3, 5, 10, 15, 20, 50; 73) = 4 + 0 = 4
∎
Media
Public domain, via Wikimedia Commons
.svg){kind=link}