{"id":8242,"date":"2023-07-04T06:00:52","date_gmt":"2023-07-04T04:00:52","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8242"},"modified":"2023-07-01T18:42:16","modified_gmt":"2023-07-01T16:42:16","slug":"04-jul-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-jul-23\/","title":{"rendered":"El problema de la mochila (mediante espacio de estados)"},"content":{"rendered":"<p>Se tiene una mochila de capacidad de peso p y una lista de n  para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el m\u00e1ximo valor posible.<\/p>\n<p>Para solucionar el problema se definen los siguientes tipos:<\/p>\n<ul>\n<li>Una soluci\u00f3n del problema de la mochila es una lista de objetos.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type SolMoch = [Objeto]\n<\/pre>\n<ul>\n<li>Los objetos son pares formado por un peso y un valor<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Objeto = (Peso,Valor)\n<\/pre>\n<ul>\n<li>Los pesos son n\u00famero enteros<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Peso = Int\n<\/pre>\n<ul>\n<li>Los valores son n\u00fameros reales.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type Valor = Float\n<\/pre>\n<ul>\n<li>Los estados del problema de la mochila son 5-tupla de la  (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el l\u00edmite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente seg\u00fan sus pesos) y s es la soluci\u00f3n parcial.<\/li>\n<\/ul>\n<pre lang=\"text\">\n     type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)\n<\/pre>\n<p>Usando el procedimiento de <a href=\"http:\/\/bit.ly\/2sqPtGs\">b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   mochila :: [Objeto] -> Peso -> (SolMoch,Valor)\n<\/pre>\n<p>tal que <code>mochila os l<\/code> es la soluci\u00f3n del problema de la mochila para la lista de objetos <code>os<\/code> y el l\u00edmite de capacidad <code>l<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   > mochila [(2,3),(3,5),(4,6),(5,10)] 8\n   ([(5,10.0),(3,5.0)],15.0)\n   > mochila [(2,3),(3,5),(5,6)] 10\n   ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n   > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35\n   ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)\n   > mochila [(2,2.8),(3,4.4),(5,6.1)] 10\n   ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule BEE_Mochila where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.List (sort)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Peso     = Int\ntype Valor    = Float\ntype Objeto   = (Peso,Valor)\ntype SolMoch  = [Objeto]\ntype NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)\n\nmochila :: [Objeto] -> Peso -> (SolMoch,Valor)\nmochila os l = (sol,v)\n  where\n    (v,_,_,_,sol) =\n      maximum (buscaProfundidad sucesoresMoch\n                                esObjetivoMoch\n                                (inicial os l))\n\n-- (inicial os l) es el estado inicial del problema de la mochila\n-- para la lista de objetos os y el l\u00edmite de capacidad l\ninicial :: [Objeto] -> Peso -> NodoMoch\ninicial os l =\n  (0,0,l,sort os,[])\n\n-- (sucesoresMoch e) es la lista de los sucesores del estado e en el\n-- problema de la mochila para la lista de objetos os y el l\u00edmite de\n-- capacidad l.\nsucesoresMoch :: NodoMoch -> [NodoMoch]\nsucesoresMoch (v,p,l,os,solp) =\n  [( v+v',\n     p+p',\n     l,\n     [o | o@(p'',_) <- os, p''>=p'],\n     (p',v'):solp )\n  | (p',v') <- os,\n    p+p' <= l]\n\n-- (esObjetivoMoch e) se verifica si e es un estado final el problema de\n-- la mochila para la lista de objetos os y el l\u00edmite de capacidad l .\nesObjetivoMoch :: NodoMoch -> Bool\nesObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    mochila [(2,3),(3,5),(4,6),(5,10)] 8\n    `shouldBe` ([(5,10.0),(3,5.0)],15.0)\n  it \"e2\" $\n    mochila [(2,3),(3,5),(5,6)] 10\n    `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n  it \"e3\" $\n    mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35\n    `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)\n  it \"e4\" $\n    mochila [(2,2.8),(3,4.4),(5,6.1)] 10\n    `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0424 seconds\n--    4 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\nPeso = int\nValor = float\nObjeto = tuple[Peso, Valor]\nSolMoch = list[Objeto]\nNodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch]\n\n# inicial(os, l) es el estado inicial del problema de la mochila\n# para la lista de objetos os y el l\u00edmite de capacidad l\ndef inicial(os: list[Objeto], l: Peso) -> NodoMoch:\n    return (0,0,l,sorted(os),[])\n\n# sucesoresMoch(e) es la lista de los sucesores del estado e en el\n# problema de la mochila para la lista de objetos os y el l\u00edmite de\n# capacidad l.\ndef sucesoresMoch(n: NodoMoch) -> list[NodoMoch]:\n    (v,p,l,os,solp) = n\n    return [( v+v1,\n              p+p1,\n              l,\n              [(p2,v2) for (p2,v2) in os if p2 >= p1],\n              [(p1,v1)] + solp )\n            for (p1,v1) in os if p + p1 <= l]\n\n# esObjetivoMoch(e) se verifica si e es un estado final el problema de\n# la mochila para la lista de objetos os y el l\u00edmite de capacidad l .\ndef esObjetivoMoch(e: NodoMoch) -> bool:\n    (_, p, l, os, _) = e\n    (p_, _) = os[0]\n    return p + p_ > l\n\ndef mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]:\n    (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch,\n                                         esObjetivoMoch,\n                                         inicial(os, l)))\n    return (sol, v)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_Mochila() -> None:\n    assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \\\n        ([(5,10.0),(3,5.0)],15.0)\n    assert mochila([(2,3),(3,5),(5,6)], 10) == \\\n        ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n    assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \\\n        ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_Mochila()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en&#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":[581],"tags":[456],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8242"}],"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=8242"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8242\/revisions"}],"predecessor-version":[{"id":8243,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8242\/revisions\/8243"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8242"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8242"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8242"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}