Skip to content

Instantly share code, notes, and snippets.

@arthur-mts

arthur-mts/cut_rod_pd.py

Created August 6, 2022 23:00
Show Gist options
  • Save arthur-mts/3650ace965a50e5367a872c969d7dd34 to your computer and use it in GitHub Desktop.
Save arthur-mts/3650ace965a50e5367a872c969d7dd34 to your computer and use it in GitHub Desktop.
Download ZIP
Resolução do problema cortes de hastes com programação dinâmica
Raw
cut_rod_pd.py
def cut_rod_pd(p, n):
memory = {}
memory[0] = 0
memory[1] = p[1]
for i in range(2, n + 1):
best_choice = p[i]
for j in range(1, i // 2 + 1):
# print(f"Haste tamanho {i}, combinação {i - j}-{j}")
choice = memory[i - j] + memory[j]
if choice > best_choice:
best_choice = choice
memory[i] = best_choice
return memory[n]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment