• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Programación Dinámica

a guest Nov 14th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import math
2.
3. def f(d,p,C,S):
4.     if p <= 0:
5.         C[0] = 0
6.         return
7.     f(d,p-1,C,S)
8.     conteo = math.inf
9.     moneda = 0
10.     for di in d:
11.         if di <= p:
12.             if C[p-di] < conteo:
13.                 conteo = C[p-di]
14.                 moneda = di
15.     C[p] = conteo + 1
16.     S[p] = moneda
17.
18. def monedas(d, n):
19.     C = [-1] * (n + 1)
20.     S = [0] * (n + 1)
21.     f(d,n,C,S)
22.     return C, S
23.
24. monto = 19
25. c, s = monedas([1, 5, 10, 20, 25, 50], monto)
26. print(c)
27. print(s)
28. contar = [0] * (monto + 1)
29. while monto > 0:
30.     print(s[monto],monto)
31.     contar[s[monto]] += 1
32.     monto -= s[monto]
33.
34. for x in range(len(contar)):
35.     if contar[x] > 0:
36.         print("Hay " + str(contar[x]) + " monedas de " + str(x))
37.
38. FIBONACCI
39.
40. import math
41.
42. cont = [0]
43. def fibo(n):
44.     t = [0]*(n+1)
45.     def fibofibo(n):
46.         cont[0] += 1
47.         if n == 1:
48.             t[0] = 0
49.             t[1] = 1
50.         else:
51.             fibofibo(n - 1)
52.             t[n] = t[n-1] + t[n-2]
53.     fibofibo(n)
54.     return t[n]
55.
56. n = 10
57. print("Fibonacci de %d es %d"%(n, fibo(n)))
58. print("Iteraciones: %d"%(cont[0]))
59.
60. def mincoins(d, p):
61.     C = [0]*(p + 1)
62.     M = [0]*(p + 1)
63.
64.     def recu(p):
65.         if p == 0:
66.             C[0] = 0
67.         else:
68.             recu(p - 1)
69.             Cother = []
70.             minimum = math.inf
71.             moneda = 0
72.             for di in d:
73.                 if p - di >= 0 and C[p-di] < minimum:
74.                     minimum = C[p-di]
75.                     moneda = di
76.
77.             C[p] = 1 + minimum
78.             M[p] = moneda
79.
80.     recu(p)
81.     return C, M
82.
83. d = [1, 5, 10, 20, 25, 50]
84. p = 40
85. C, M = mincoins(d, p)
86. print(C)
87. print(M)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top