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

 

 


Tema destacado: Estamos en la red social de Mastodon


+  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,408 veces)
jca1

Desconectado Desconectado

Mensajes: 59


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: 59


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: 59


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: 59


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: 59


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: 59


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,876 Último mensaje 8 Diciembre 2010, 17:55 pm
por Littlehorse
Problema de mochila hardlock
Ingeniería Inversa 		diantred 0 2,363 Último mensaje 2 Octubre 2012, 06:41 am
por diantred
Problema con mochila (dongle o llave)
Seguridad 		diantred 0 3,145 Ú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,782 Último mensaje 8 Febrero 2017, 16:20 pm
por Geovane
Problema de la mochila (binaria)
Programación General 		jca1 4 3,451 Último mensaje 3 Septiembre 2019, 19:18 pm
por WHK
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines