Sea S un conjunto finito de n\u00fameros naturales y m un n\u00famero natural. El problema consiste en determinar si existe un subconjunto de S cuya suma es m. Por ejemplo, si S = [3,34,4,12,5,2] y m = 9, existe un subconjunto de S, [4,5], cuya suma es 9. En cambio, no hay ning\u00fan subconjunto de S que sume 13.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n existeSubSuma :: [Int] -> Int -> Bool\n<\/pre>\ntal que (existeSubSuma xs m) se verifica si existe alg\u00fan subconjunto de xs que sume m. Por ejemplo,<\/p>\n
\n existeSubSuma [3,34,4,12,5,2] 9 == True\n existeSubSuma [3,34,4,12,5,2] 13 == False\n existeSubSuma ([3,34,4,12,5,2]++[20..400]) 13 == False\n existeSubSuma ([3,34,4,12,5,2]++[20..400]) 654 == True\n existeSubSuma [1..200] (sum [1..200]) == True\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (subsequences, sort)\nimport Data.Array (Array, array, listArray, (!))\n \n-- 1\u00aa definici\u00f3n (Calculando todos los subconjuntos)\n-- =================================================\n \nexisteSubSuma1 :: [Int] -> Int -> Bool\nexisteSubSuma1 xs n =\n any (\\ys -> sum ys == n) (subsequences xs)\n \n-- 2\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n \nexisteSubSuma2 :: [Int] -> Int -> Bool\nexisteSubSuma2 _ 0 = True\nexisteSubSuma2 [] _ = False\nexisteSubSuma2 (x:xs) n\n | n < x = existeSubSuma2 xs n\n | otherwise = existeSubSuma2 xs (n-x) || existeSubSuma2 xs n \n \n-- 3\u00aa definici\u00f3n (por programaci\u00f3n din\u00e1mica)\n-- =========================================\n \nexisteSubSuma3 :: [Int] -> Int -> Bool\nexisteSubSuma3 xs n =\n matrizExisteSubSuma3 xs n ! (length xs,n) \n \n-- (matrizExisteSubSuma3 xs m) es la matriz q tal que q(i,j) se verifica\n-- si existe alg\u00fan subconjunto de (take i xs) que sume j. Por ejemplo,\n-- \u03bb> elems (matrizExisteSubSuma3 [1,3,5] 9)\n-- [True,False,False,False,False,False,False,False,False,False,\n-- True,True, False,False,False,False,False,False,False,False,\n-- True,True, False,True, True, False,False,False,False,False,\n-- True,True, False,True, True, True, True, False,True, True]\n-- Con las cabeceras,\n-- 0 1 2 3 4 5 6 7 8 9\n-- [] [True,False,False,False,False,False,False,False,False,False,\n-- [1] True,True, False,False,False,False,False,False,False,False,\n-- [1,3] True,True, False,True, True, False,False,False,False,False,\n-- [1,3,5] True,True, False,True, True, True, True, False,True, True]\nmatrizExisteSubSuma3 :: [Int] -> Int -> Array (Int,Int) Bool\nmatrizExisteSubSuma3 xs n = q\n where m = length xs\n v = listArray (1,m) xs\n q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m],\n j <- [0..n]]\n f _ 0 = True\n f 0 _ = False\n f i j | j < v ! i = q ! (i-1,j)\n | otherwise = q ! (i-1,j-v!i) || q ! (i-1,j)\n \n-- 4\u00aa definici\u00f3n (ordenando y por recursi\u00f3n)\n-- =========================================\n \nexisteSubSuma4 :: [Int] -> Int -> Bool\nexisteSubSuma4 xs = aux (sort xs)\n where aux _ 0 = True\n aux [] _ = False\n aux (y:ys) n\n | y <= n = aux ys (n-y) || aux ys n\n | otherwise = False\n \n-- 5\u00aa definici\u00f3n (ordenando y din\u00e1mica)\n-- ====================================\n \nexisteSubSuma5 :: [Int] -> Int -> Bool\nexisteSubSuma5 xs n =\n matrizExisteSubSuma5 (reverse (sort xs)) n ! (length xs,n) \n \nmatrizExisteSubSuma5 :: [Int] -> Int -> Array (Int,Int) Bool\nmatrizExisteSubSuma5 xs n = q\n where m = length xs\n v = listArray (1,m) xs\n q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m],\n j <- [0..n]]\n f _ 0 = True\n f 0 _ = False\n f i j | v ! i <= j = q ! (i-1,j-v!i) || q ! (i-1,j) \n | otherwise = False\n \n-- Equivalencia\n-- ============\n \nprop_existeSubSuma :: [Int] -> Int -> Bool\nprop_existeSubSuma xs n =\n all (== existeSubSuma2 ys m) [ existeSubSuma3 ys m\n , existeSubSuma4 ys m\n , existeSubSuma5 ys m ]\n where ys = map abs xs\n m = abs n\n \n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_existeSubSuma\n-- +++ OK, passed 100 tests.\n \n-- Comparaci\u00f3n de eficiencia:\n-- ==========================\n\n-- \u03bb> let xs = [1..22] in existeSubSuma1 xs (sum xs)\n-- True\n-- (7.76 secs, 3,892,403,928 bytes)\n-- \u03bb> let xs = [1..22] in existeSubSuma2 xs (sum xs)\n-- True\n-- (0.02 secs, 95,968 bytes)\n-- \u03bb> let xs = [1..22] in existeSubSuma3 xs (sum xs)\n-- True\n-- (0.03 secs, 6,055,200 bytes)\n-- \u03bb> let xs = [1..22] in existeSubSuma4 xs (sum xs)\n-- True\n-- (0.01 secs, 98,880 bytes)\n-- \u03bb> let xs = [1..22] in existeSubSuma5 xs (sum xs)\n-- True\n-- (0.02 secs, 2,827,560 bytes)\n \n-- \u03bb> let xs = [1..200] in existeSubSuma2 xs (sum xs)\n-- True\n-- (0.01 secs, 182,280 bytes)\n-- \u03bb> let xs = [1..200] in existeSubSuma3 xs (sum xs)\n-- True\n-- (8.89 secs, 1,875,071,968 bytes)\n-- \u03bb> let xs = [1..200] in existeSubSuma4 xs (sum xs)\n-- True\n-- (0.02 secs, 217,128 bytes)\n-- \u03bb> let xs = [1..200] in existeSubSuma5 xs (sum xs)\n-- True\n-- (8.66 secs, 1,875,087,976 bytes)\n--\n-- \u03bb> and [existeSubSuma2 [1..20] n | n <- [1..sum [1..20]]]\n-- True\n-- (2.82 secs, 323,372,512 bytes)\n-- \u03bb> and [existeSubSuma3 [1..20] n | n <- [1..sum [1..20]]]\n-- True\n-- (0.65 secs, 221,806,376 bytes)\n-- \u03bb> and [existeSubSuma4 [1..20] n | n <- [1..sum [1..20]]]\n-- True\n-- (4.12 secs, 535,153,152 bytes)\n-- \u03bb> and [existeSubSuma5 [1..20] n | n <- [1..sum [1..20]]]\n-- True\n-- (0.73 secs, 238,579,696 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Sea S un conjunto finito de n\u00fameros naturales y m un n\u00famero natural. El problema consiste en determinar si existe un subconjunto de S cuya suma es m. Por ejemplo, si S = [3,34,4,12,5,2] y m = 9, existe un subconjunto de S, [4,5], cuya suma es 9. En cambio, no hay ning\u00fan subconjunto de…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[250,8,286,38,28,72,42,181,141,11,6,32,14,88,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3977"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=3977"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3977\/revisions"}],"predecessor-version":[{"id":4017,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3977\/revisions\/4017"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3977"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3977"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3977"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}