elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Únete al Grupo Steam elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Problema de la mochila
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema de la mochila  (Leído 5,041 veces)
jca1

Desconectado Desconectado

Mensajes: 58


Ver Perfil
Problema de la mochila
« 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?


En línea

jca1

Desconectado Desconectado

Mensajes: 58


Ver Perfil
Re: Problema de la mochila
« Respuesta #1 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.


« Última modificación: 20 Diciembre 2021, 23:28 pm por jca1 » En línea

jca1

Desconectado Desconectado

Mensajes: 58


Ver Perfil
Re: Problema de la mochila
« Respuesta #2 en: 28 Diciembre 2021, 09:42 am »

(Anexo a la respuesta anterior)

dado el siguiente caso:

Código:

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
« Última modificación: 28 Diciembre 2021, 10:13 am por jca1 » En línea

jca1

Desconectado Desconectado

Mensajes: 58


Ver Perfil
Re: Problema de la mochila
« Respuesta #3 en: 9 Enero 2022, 23:45 pm »

(Continuacion de otro caso)

Código:
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?
En línea

jca1

Desconectado Desconectado

Mensajes: 58


Ver Perfil
Re: Problema de la mochila
« Respuesta #4 en: 17 Enero 2022, 07:38 am »

Voy a proponer un caso mas "simple", con 50 item.
Código:
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?
« Última modificación: 20 Enero 2022, 02:57 am por jca1 » En línea

jca1

Desconectado Desconectado

Mensajes: 58


Ver Perfil
Re: Problema de la mochila
« Respuesta #5 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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
problema de la mochila en c!!
Programación C/C++
Janfry 4 14,478 Último mensaje 8 Diciembre 2010, 17:55 pm
por Littlehorse
Problema de mochila hardlock
Ingeniería Inversa
diantred 0 2,163 Último mensaje 2 Octubre 2012, 06:41 am
por diantred
Problema con mochila (dongle o llave)
Seguridad
diantred 0 2,869 Último mensaje 12 Octubre 2012, 05:49 am
por diantred
Saltar la mochila de un software que no usa mochila.
Ingeniería Inversa
GS2013 7 7,102 Último mensaje 8 Febrero 2017, 16:20 pm
por Geovane
Problema de la mochila (binaria)
Programación General
jca1 4 3,133 Último mensaje 3 Septiembre 2019, 19:18 pm
por WHK
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines