Título: Problema de la mochila
Publicado por: jca1 en 16 Diciembre 2021, 07:03 am
Un programa que resuelva con un resultado aproximado al optimo en este problema, cuanto seria un rango de "garantia" de aproximacion para que sea considerado util?
Por ejemplo un programa que te asegure el 1% de margen es bueno?
Título: Re: Problema de la mochila
Publicado por: jca1 en 20 Diciembre 2021, 20:27 pm
(No se si es posible responder un tema propio primero esta permitido, porque no puedo editar el inical)
Pregunte lo anterior porque hice un programa que resuelve el problema de forma eficaz, aunque a veces tarda bastante siempre en pocos segundos me devuelve soluciones bastante aproximadas a la optima o encuentra la optima en ese momento.
Por ejemplo para un caso de n=160, siendo n la cantidad de elementos posibles para incorporar, dependediendo de la capacidad de la mochila, tarda en encontrar la solucion optima en una hora o 10 horas incluyendo verificandolo, por dos casos que probe. Con otros casos para ese n o mayor lo resolvio en un par de segundos.
No importa el tamaño de la entrada para el tiempo de ejecucion. Por ejemplo si la capacidad es de 100 o 1000000000 no modifica el tiempo de ejecucion del mismo.
Necesito algun caso que sea representativo para verficar la eficiencia. Por ejemplo para n=10 0.
Título: Re: Problema de la mochila
Publicado por: jca1 en 28 Diciembre 2021, 09:42 am
(Anexo a la respuesta anterior) dado el siguiente caso: N.º Peso Valor 1 14588629582201 5276815605906449 2 164481749688609 5309583717329863 3 205730373531307 5329619489437584 4 252647202569584 5351726706158925 5 294237552790977 5402634651035046 6 415181102709367 5405325301196649 7 434780283185498 5417046718888412 8 465917639958693 5418284601208041 9 554402676232595 5475914904362073 10 570762890865167 5509074226169616 11 676948759488896 5512123417247576 12 722432831098187 5586140217535448 13 724431178666991 5605648760042149 14 750115619388679 5659147215091773 15 767532286296282 5672758862613367 16 805479261049720 5718541164990366 17 933983003197288 5755950295957769 18 964903427617290 5817984823603671 19 968909610981529 5828974554324587 20 997164240119792 5881242195696504 21 1048554293757143 5955109549493639 22 1085570198596243 5970191308655077 23 1098851601119926 6021398401233982 24 1147687850942615 6057551745848646 25 1148433096804838 6279047299857968 26 1188411530030867 6366904495894766 27 1271938645908964 6393860287734480 28 1357117387177604 6519366374354713 29 1447195478900452 6551646480181343 30 1556534107790089 6557613168721194 31 1559119676724087 6590444598501222 32 1580471353626150 6629364614158954 33 1735225735130097 6696299838863670 34 1759133415526008 6697415756909721 35 1813730017820853 6699162991267490 36 1892357073236775 6735135925533815 37 1911259514509681 6764895627970755 38 1958167030106420 6770695126240527 39 1988235790360112 6783967615583307 40 2004018705707521 6830595071813376 41 2141104984662408 6837461712643138 42 2207317799259911 6911539385457124 43 2305245458608990 6951880747850561 44 2353285882893806 7199704563057061 45 2363762300213971 7228569651257108 46 2415912643427303 7280963172091236 47 2483335978970459 7285338167243996 48 2527310498394226 7290912494886235 49 2551558082842607 7331439557342070 50 2592323784553049 7414104963913833 51 2618462919006518 7417190758670783 52 2725340604879525 7451375374319646 53 2821191984321125 7456898659281466 54 2835636356341224 7524400557383184 55 2919694296870452 7556547691726496 56 3117855357230428 7643253397123820 57 3145882483177681 7672510310469968 58 3148517125221016 7715429902735608 59 3173753865595647 7771322288053085 60 3360562551278537 7914394010025391 61 3361737942812948 7927626434187542 62 3386568927394721 8062225188866445 63 3524312511843557 8066243838157770 64 3599003372021800 8097518611056720 65 3687280612987549 8287348439310476 66 3715781931278740 8383792061193192 67 3751158179366618 8398655622974535 68 3774487286153027 8519605300856544 69 3854286562672970 8611492791577488 70 3922938816117466 8618636776076155 71 3924102778834234 8656646539594801 72 3987367808660507 8719642379543156 73 3992220686647404 8798177552369334 74 4067815889695279 8831336822336017 75 4081090309524788 8984045549919634 76 4091090835755164 9067607970045600 77 4126990037052735 9196866186462930 78 4192980163989298 9239464367406860 79 4202952786124747 9306314970030520 80 4210642310426149 9329299874734760 81 4548566581986690 9346681178913830 82 4610897182334249 9366482189852440 83 4700747016242553 9374307609037140 84 4700763956342967 9395374111692680 85 4747516552870209 9405008740374730 86 4799519192435085 9417045063565950 87 4826205978907101 9515829014412590 88 4850454702930504 9542452333533330 89 4868109181475080 9544057672078040 90 4892015341643560 9596261329102120 91 4948212836341631 9615077594608100 92 4949994894249733 9616473285575660 93 4984917788690850 9641239080722050 94 5006490721341773 9668840597169840 95 5102409351675896 9680754460736420 96 5106902448954033 9738354540800340 97 5181181650349445 9738453838963910 98 5191189542489884 9826278439510520 99 5232372271067336 9902150581273970 100 5239315202757033 9991436711981470
Existe algun programa que lo resuelva de manera eficaz y relativamente de manera eficiente, para un capacidad de la mochila de 30000000000000000 ? Para este caso especifico pude conseguir el resultado mas optimo, encontrandolo y verificandolo como tal en 1 segundo. P.D.: es cierto que la relacion entre los pesos y valores favorecen a la eleccion de la mejor solucion. Proximamente voy a mostrar otro caso y a ver como lo resuelve
Título: Re: Problema de la mochila
Publicado por: jca1 en 9 Enero 2022, 23:45 pm
(Continuacion de otro caso) Num item peso valor 1 100994605112948 1963179050967 2 102022134281554 1019379407177 3 103256115462428 1462123912225 4 103907042203309 1688376540471 5 104007315862560 1590071264489 6 104182552867613 1495211372290 7 104540965259464 1061860514925 8 104945580169773 1429067551838 9 105241663762759 1484491105804 10 105327231528853 1125780424573 11 105896491474635 1096329231943 12 106661131604024 1480051875887 13 106898318312442 1831414197459 14 108061952456727 1254639524006 15 108171398806571 1194405446782 16 108212745233530 1134293780438 17 108350471777617 1793145695028 18 108578386970601 1829217508306 19 108622748562385 1170402236306 20 108898976839498 1561004449247 21 109731322616189 1330182386478 22 110433203842420 1866464231537 23 110433445639043 1010130896184 24 110588837094783 1166155032415 25 110605916584236 1478285935181 26 111054618610560 1189098149680 27 112650680858511 1744474796045 28 112936344987936 1889137305603 29 114351573735119 1117866225051 30 114839375165506 1423746374225 31 114993906655174 1927502850672 32 116507278249994 1645620054180 33 116533157796190 1367885875296 34 116810829930086 1953651684495 35 117273721806045 1607351523043 36 117692600475376 1030831479792 37 117805252992795 1856307348042 38 118956737210390 1898044977597 39 119663787751672 1886553320219 40 119754211136363 1907187809074 41 120912254916732 1139758291651 42 121104511274446 1583869874141 43 121251686253141 1829242253785 44 121408987756850 1559900892566 45 121862299469822 1470323401196 46 122368388175709 1724494596187 47 122742986965478 1290276109505 48 123537116685854 1521321057041 49 124442478655644 1112783674264 50 124853587809997 1569282871268 51 125140435710208 1360813812104 52 126317994079461 1243785243891 53 128426957645062 1353329212248 54 128911871892170 1099823847680 55 128960569308273 1024926896240 56 130170770737443 1006678520408 57 131166929364433 1572106060312 58 131456631520260 1360210121844 59 132347147985089 1334601670292 60 132417180354335 1280539329421 61 132607005326848 1502956411462 62 134045634745689 1428523889646 63 134230860902023 1210896866547 64 134301765792828 1495726980888 65 136144444237411 1433252859855 66 136569662394359 1823783928378 67 136818070259696 1166046043074 68 137214076668152 1138649588608 69 137500202074650 1580090854178 70 138138438270547 1758041405382 71 138559381391529 1307151027698 72 139231712896686 1239084084959 73 139549991225279 1293981279153 74 140176324684910 1916305238397 75 140388219460392 1907381692118 76 140468517523650 1692360389236 77 141035337846340 1818828440309 78 141364884354316 1713197398375 79 141410578095892 1672939516720 80 141627896357559 1350518314200 81 141692148557828 1223706063771 82 142040732061695 1354733992845 83 142203107675544 1627699154455 84 142452656967800 1658977638948 85 142697949488286 1391257980782 86 143006091163531 1748529756579 87 143536132382507 1082209976242 88 145048772276835 1421431737199 89 145363692207586 1543506553116 90 145620823333912 1493009900323 91 145826207371695 1765445344140 92 145841368716535 1671200215551 93 146395012020520 1232307290421 94 147093288550353 1740945936480 95 147632147133647 1021974543560 96 148634256987789 1048475197525 97 149390128734077 1732978867472 98 149672343172173 1496608714766 99 149788216284136 1178362652374 100 150240077799104 1956839562009
Para este caso con una capacidad de 1400000000000000 lo resolvio en menos de un minuto. No use programacion dinamica. que opinan?
Título: Re: Problema de la mochila
Publicado por: jca1 en 17 Enero 2022, 07:38 am
Voy a proponer un caso mas "simple", con 50 item. Item Peso Valor 1 101216066775657 131363839117837 2 101405972061117 132065706231834 3 102601515609973 132484448479051 4 104352044471043 133131532988999 5 104746786834633 134282309873776 6 105390113261536 134354880265164 7 105431679530268 135046566038982 8 106144070034379 136001709139178 9 106173044863867 136385117866201 10 106183414763863 138048091255272 11 107922299411955 138166955521491 12 107929460964952 138523390409357 13 108291199768876 138720295660798 14 108616122657291 138958209501845 15 109481832105485 138970927009628 16 109611142582387 138971988095107 17 110121878313456 139634767761933 18 111818679339917 139789094059708 19 114575808944835 140040919275085 20 115513475976547 140106671421024 21 115967930092736 140362195999036 22 116178979841777 140629655922363 23 117137317712528 141607624727110 24 117146617876000 142972667574445 25 117659789964154 143077697300132 26 118697836149994 143377042479088 27 118772685896622 143461969069446 28 119116894778240 144719700598168 29 119678700918499 145730047759370 30 120464718958840 146376221628128 31 120837555496468 146958645818433 32 121630756979528 147577502412275 33 121950507577377 147621628352184 34 122531814595343 148166192102550 35 123180539453324 149110471743748 36 123700434405359 149119917493970 37 123806883160215 149495225206337 38 123851638266936 149535328368965 39 125968256513188 149903789775847 40 126327257133379 151830493298231 41 127304781278971 151984268376262 42 127358397257638 152268390536176 43 128094297114028 152982572668723 44 128795518647103 153564607037044 45 129019203882586 154243241953725 46 129672046076623 154400734089124 47 130072434457701 154433268138144 48 130330694754605 154893353823209 49 131203592485271 154955091377872 50 131232299362321 155192570500134
Para la capacidad de 1500000000000000, cual es la mejor solucion? Les paso mi resultado: Los items que hay que elegir son: 2,3,5,7,8,9,10,12,14,15,17,18,25,50. (La solucion la encontre en menos de un segundo) Es la optima? Segun mi algoritmo si Alguien lo pudo comprobar?
Título: Re: Problema de la mochila
Publicado por: jca1 en 22 Enero 2022, 00:16 am
Hola, si alguien quiere proponer una caso de tamaño hasta 100.
Cuando lo resuelva les paso los datos del resultado y tiempo.
Pueden ser los valores de entradas de magnitud similar a los que puse.
Si lo resuelven estaría bueno comparar resultados.
|