Suma de subconjuntos. Enumeración. Subset sum. Enumeration.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
| 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}
Congratulations @j2e2xae! You have completed the following achievement on the Hive blockchain And have been rewarded with New badge(s)
Your next target is to reach 600 upvotes.
You can view your badges on your board and compare yourself to others in the Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOP