problema de la mochila<\/a> (en ingl\u00e9s Knapsack) concretamente se trataba de una variante 0\/1 con repetici\u00f3n de \u00edtems y con restricciones con el n\u00famero de \u00edtems. Le digo si sabe hacer la pr\u00e1ctica para un Knapsack. Me contesta que cree que si porque en clase el profesor us\u00f3 ese problema en varias explicaciones. Se pone manos a la obre y obtiene el programa que resolv\u00eda el problema de la mochila en C++ en las cuatro versiones que le ped\u00edan.<\/p>\nPero no lograba un resultado correcto. No se aclaraba con la parte del algoritmo que ten\u00eda que usar las restricciones sobre el n\u00famero de art\u00edculos. Me vuelve a preguntar. Me pongo a pensar y doy con una soluci\u00f3n: usar las restricciones de los n\u00fameros de art\u00edculos para crear tantos art\u00edculos iguales como el m\u00e1ximo de art\u00edculos iguales permitidos para el art\u00edculo en concreto. Le hab\u00edan dado varios casos de prueba, as\u00ed que cogemos uno f\u00e1cil y a mano construimos las nuevas cargas para el programa\u2026 y funcionaba. De hecho, busco en la teor\u00eda y hay varios autores que dicen que es tal vez la soluci\u00f3n m\u00e1s eficiente. Mi hijo prepara una funci\u00f3n que transforma los datos de entrada que le proporcionan en tantos art\u00edculos diferentes del mismo tipo para poder usar su rutina de la mochila 0\/1.<\/p>\n
Sigue con las pruebas y se da cuenta que en los casos de prueba donde hay muchos art\u00edculos al multiplicar el n\u00famero de art\u00edculos con su funci\u00f3n el tiempo de ejecuci\u00f3n sube mucho. Sobre todo, en las versiones menos eficientes del algoritmo. Vuelve a coment\u00e1rmelo. Aqu\u00ed yo ya empiezo a darme cuenta del error que comet\u00ed al irme a buscar una soluci\u00f3n r\u00e1pida tirando por la calle de en medio. Es la costumbre de buscar resultados pronto y r\u00e1pido. Vuelvo a la teor\u00eda y encuentro una soluci\u00f3n. Se trata de aplicar una f\u00f3rmula para crear los nuevos art\u00edculos usando sumas de potencias de 2 y promediando el valor y el peso. De esta manera un art\u00edculo que deb\u00edamos repetir 1.500 veces seg\u00fan los datos de entrada, se convert\u00eda solo en 7 art\u00edculo. A pesar de la demostraci\u00f3n matem\u00e1tica mi reto\u00f1o no lo ve\u00eda claro. As\u00ed que tuve que repasar lo que sab\u00eda de C++ y cambi\u00e9 su rutina por la nueva. Hicimos las pruebas y los resultados eran correctos. Adem\u00e1s ahora el tiempo de ejecuci\u00f3n bajaba much\u00edsimo.<\/p>\n
Pero en la pr\u00e1ctica en el \u00faltimo punto ped\u00edan que mostr\u00e1semos una lista con los art\u00edculos escogidos por el algoritmo y cuando de ellos hab\u00edamos seleccionado. Al hacerlo sobre una lista de art\u00edculos nueva (los creados por nosotros para poder usar un algoritmo 0\/1 b\u00e1sico) los resultados que obten\u00edamos no encajaban con los datos que se ped\u00edan.<\/p>\n
Al final segu\u00ed con el C++ sobre todo porque me sent\u00eda culpable. Yo hab\u00eda marcado el camino mal con mi primer consejo. Entre los dos montamos otro juego de funciones que eran capaces de reconvertir las soluciones con el grupo de art\u00edculos nuevos y convertirlas a los art\u00edculos originales. Y todo funcionaba bien, menos mal.<\/p>\n
Pero me puse a calcular el tiempo que hab\u00edamos invertido en todas las funciones accesorias que hab\u00edamos programado para no modificar el primer algoritmo de la mochila 0\/1 y me di cuenta del gran error. Si hubiese le\u00eddo todas las especificaciones y hubiese revisado los casos de pruebas habr\u00eda empezado de otra forma y no habr\u00eda usado una funci\u00f3n de mochila 0\/1 cambiando los datos de entrada. Pero es lo malo de estar acostumbrado a ir deprisa solucionando problemas.<\/p>\n
De todas formas, no me ha parecido una experiencia negativa. Por un lado, yo he vuelto a programar en C++ y a pelearme con algoritmos y problemas abstractos. Por otro lado, mi hijo ha aprendido una lecci\u00f3n doble: pensar bien las soluciones r\u00e1pidas que le da su padre antes de implementarlas y la importancia de pensar, razonar, leer todas las especificaciones, ver con atenci\u00f3n los casos de pruebas y hacer muchos diagramas antes de ponerse a codificar. Y por cierto las funciones para decodificar la soluci\u00f3n que ten\u00edamos y convertirla en los art\u00edculos buscados fueran tambi\u00e9n buenas pr\u00e1cticas de algoritmia y eficiencia\u2026<\/p>\n
As\u00ed que esta semana est\u00e1 con otra pr\u00e1ctica que tambi\u00e9n se parece mucho al problema de la mochila\u2026 pero esta vez lo ha enfocado de forma diferente\u2026 y con la d\u00e9cima parte de c\u00f3digo su programa funciona bien. Por lo menos va aprendiendo la lecci\u00f3n de que muchas veces es mejor pensar que ponerse r\u00e1pidamente a resolver el problema a pesar de que tenemos una idea que nos parece muy buena y que est\u00e1 apoyada por autores de renombre.<\/p>\n","protected":false},"excerpt":{"rendered":"
El otro d\u00eda contaba un caso donde los a\u00f1os de experiencia te hace ver pronto una soluci\u00f3n a un problema. Hoy voy con el caso contrario: a veces la experiencia y lo que yo llamo resultismo o b\u00fasqueda de eficacia de muchos a\u00f1os de trabajo pueden ser contraproducentes. Sobre todo, si adem\u00e1s se le a\u00f1ade […]<\/p>\n","protected":false},"author":1,"featured_media":17965,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[10,13],"tags":[3601,760,3600,3599],"series":[],"class_list":["post-17966","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-otras-cosas","category-software","tag-algoritmos","tag-datos","tag-knapsack-0-1","tag-problema-de-la-mochila"],"_links":{"self":[{"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/posts\/17966","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/comments?post=17966"}],"version-history":[{"count":0,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/posts\/17966\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/media\/17965"}],"wp:attachment":[{"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/media?parent=17966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/categories?post=17966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/tags?post=17966"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/changlonet.com\/blog\/wp-json\/wp\/v2\/series?post=17966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"https:\/\/changlonet.com\/blog\/wp-content\/uploads\/2021\/04\/042221_1608_Lomalodelaa1.jpg\" "\\"\\"")
<\/p>\n