0votos

función resuelveSumas en Other

por josejuan usando lp_solve hace 5 años

El problema generalizado (cualquier número de sumandos) es NP-completo; puede establecerse la misma estrategia de la solución anterior pero en lugar de 2 sumandos varios, no cambiaría mucho; por poner la forma "canónica" de resolverlo, pongo aquí una solución usando programación lineal binaria.

programar, utilizando Hugs una función resuelveSumas que dada una tupla formada por una lista de resultados y una lista de sumandos, devuelva una cadena de caracteres indicando si el problema tiene solución y si ésta es única o no.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/* 
 
    El problema general solicitado (cualquier número de sumandos) es 
    NP-completo, porque puede reducirse a él trivialmente el problema 
    de "subset sum" http://en.wikipedia.org/wiki/Subset_sum_problem. 
     
    Es decir, no se conoce ningún algoritmo eficiente que resuelva el 
    problema de forma exacta. 
     
    Así, lo mejor es usar los mejores solvers para problemas NP-completos. 
     
    Aquí, se resuelve la instancia usando `lp_solve` 
     
        rs := { 10, 12 } 
        xs := { 2, 2, 2, 4, 4, 4, 4 } 
     
    Pero puede hacerse un programa (ej. en Haskell) fácilmente como en 
    todas estas otras soluciones: 
     
        http://www.solveet.com/exercises/Camino-de-Hamilton/192/solution-1346 
        http://www.solveet.com/exercises/Spotify-trafico-de-influencias/137/solution-951 
        http://www.solveet.com/exercises/Programacion-dinamica-problema-de-tubo-de-chocolates/170/solution-1224 
        http://www.solveet.com/exercises/Minimal-Superpermutations/188/solution-1318 
        http://www.solveet.com/exercises/Llenando-el-tetris/249/solution-1700 
        http://www.solveet.com/exercises/Subsecuencias-monotonicas-crecientes-en-C/172/solution-1237 
        http://www.solveet.com/exercises/Mejor-factorizacion-triple/240/solution-1616 
 
*/ 
 
min: x11 + x12 + x13 + x14 + x15 + x16 + x17 + x21 + x22 + x23 + x24 + x25 + x26 + x27; 
 
2 x11 + 2 x12 + 2 x13 + 4 x14 + 4 x15 + 4 x16 + 4 x17 = 10; 
2 x21 + 2 x22 + 2 x23 + 4 x24 + 4 x25 + 4 x26 + 4 x27 = 12; 
 
x11 + x21 = 1; 
x12 + x22 = 1; 
x13 + x23 = 1; 
x14 + x24 = 1; 
x15 + x25 = 1; 
x16 + x26 = 1; 
x17 + x27 = 1; 
 
bin x11, x12, x13, x14, x15, x16, x17, x21, x22, x23, x24, x25, x26, x27; 
 
/* 
 
josejuantmp$ lp_solve p.lp 
 
Value of objective function: 7.00000000 
 
Actual values of the variables: 
x11                             1 
x12                             1 
x13                             1 
x14                             0 
x15                             0 
x16                             1 
x17                             0 
x21                             0 
x22                             0 
x23                             0 
x24                             1 
x25                             1 
x26                             0 
x27                             1 
 
Es decir: 
 
  2 + 2 + 2         + 4     = 10 
              4 + 4     + 4 = 12 
 
*/ 
2 comentarios

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.