{"id":2220,"date":"2016-03-11T06:00:34","date_gmt":"2016-03-11T04:00:34","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2220"},"modified":"2016-03-28T07:48:46","modified_gmt":"2016-03-28T05:48:46","slug":"maxima-suma-en-una-matriz","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maxima-suma-en-una-matriz\/","title":{"rendered":"M\u00e1xima suma en una matriz"},"content":{"rendered":"<p>Las matrices puede representarse mediante tablas cuyos \u00edndices son pares de n\u00fameros naturales:<\/p>\n<pre lang=\"text\">\n   type Matriz = Array (Int,Int) Int\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maximaSuma :: Matriz -> Int\n<\/pre>\n<p>tal que (maximaSuma p) es el m\u00e1ximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece s\u00f3lo a una fila y a una columna. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ghci> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])\n   17\n<\/pre>\n<p>ya que las selecciones, y sus sumas, de la matriz<\/p>\n<pre lang=\"text\">\n   |1 2 3|\n   |8 4 9|\n   |5 6 7|\n<\/pre>\n<p>son<\/p>\n<pre lang=\"text\">\n   [1,4,7] --> 12\n   [1,9,6] --> 16\n   [2,8,7] --> 17\n   [2,9,5] --> 16\n   [3,8,6] --> 17\n   [3,4,5] --> 12\n<\/pre>\n<p>Hay dos selecciones con m\u00e1xima suma: [2,8,7] y [3,8,6].<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array\nimport Data.List (permutations)\n\ntype Matriz = Array (Int,Int) Int\n\nmaximaSuma :: Matriz -> Int\nmaximaSuma p = maximum [sum xs | xs <- selecciones p]\n\n-- (selecciones p) es la lista de las selecciones en las que cada\n-- elemento pertenece a un \u00fanica fila y a una \u00fanica columna de la matriz\n-- p. Por ejemplo,\n--    ghci> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])\n--    [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]]\nselecciones :: Matriz -> [[Int]]\nselecciones p = \n    [[p!(i,j) | (i,j) <- ijs] | \n     ijs <- [zip [1..n] xs | xs <- permutations [1..n]]] \n    where (_,(m,n)) = bounds p\n\n-- 2\u00aa soluci\u00f3n (mediante submatrices):\nmaximaSuma2 :: Matriz -> Int\nmaximaSuma2 p \n    | (m,n) == (1,1) = p!(1,1)\n    | otherwise = maximum [p!(1,j) \n                  + maximaSuma2 (submatriz 1 j p) | j <- [1..n]]\n    where (_,(m,n)) = bounds p\n\n-- (submatriz i j p) es la matriz obtenida a partir de la p eliminando\n-- la fila i y la columna j. Por ejemplo, \n--    ghci> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])\n--    array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)]\nsubmatriz :: Int -> Int -> Matriz -> Matriz\nsubmatriz i j p = \n    array ((1,1), (m-1,n -1))\n          [((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]]\n    where (_,(m,n)) = bounds p\n          f k l | k < i  &#038;&#038; l < j  = (k,l)\n                | k >= i && l < j  = (k+1,l)\n                | k < i  &#038;&#038; l >= j = (k,l+1)\n                | otherwise        = (k+1,l+1)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Las matrices puede representarse mediante tablas cuyos \u00edndices son pares de n\u00fameros naturales: type Matriz = Array (Int,Int) Int Definir la funci\u00f3n maximaSuma :: Matriz -> Int tal que (maximaSuma p) es el m\u00e1ximo de las sumas de las listas de elementos de la matriz p tales que cada elemento pertenece s\u00f3lo a una fila&#8230;<\/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":[7],"tags":[43,8,42,15,228,6,40,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2220"}],"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=2220"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2220\/revisions"}],"predecessor-version":[{"id":2250,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2220\/revisions\/2250"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}