Problema de la mochila

[jca1]

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?

[jca1]

(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.

[jca1]

(Anexo a la respuesta anterior)

dado el siguiente caso:

Código [Seleccionar] Expandir


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