62 lines
1.4 KiB
Python
62 lines
1.4 KiB
Python
import time
|
|
|
|
|
|
def simple_cut_rod(p, n):
|
|
if n == 0:
|
|
return 0
|
|
q = float('-inf')
|
|
for i in range(1, n + 1):
|
|
q = max(q, p[i] + simple_cut_rod(p, n - i))
|
|
return q
|
|
|
|
|
|
def _memoized_cut_rod_aux(p, n, r):
|
|
if r[n] >= 0:
|
|
return r[n]
|
|
if n == 0:
|
|
q = 0
|
|
else:
|
|
q = float('-inf')
|
|
for i in range(1, n + 1):
|
|
q = max(q, p[i] + _memoized_cut_rod_aux(p, n - i, r))
|
|
r[n] = q
|
|
return q
|
|
|
|
|
|
def memoized_cut_rod(p, n):
|
|
r = [float('-inf')] * (n + 1)
|
|
return _memoized_cut_rod_aux(p, n, r)
|
|
|
|
|
|
def bottom_up_cut_rod(p, n):
|
|
r = [0] * (n + 1)
|
|
for j in range(1, n + 1):
|
|
q = float('-inf')
|
|
for i in range(1, j + 1):
|
|
q = max(q, p[i] + r[j - i])
|
|
r[j] = q
|
|
return r[n]
|
|
|
|
|
|
def main():
|
|
n = int(input("Enter number of Inches: "))
|
|
|
|
with open("Cut Rod Problem/Cut Rod Problem/Data.txt", encoding="utf-8-sig") as f:
|
|
price_data = f.read().split()
|
|
|
|
# 1-indexed: prices[0] unused, prices[i] = price for length i
|
|
prices = [0] + [int(x) for x in price_data]
|
|
|
|
start = time.perf_counter()
|
|
best_price = memoized_cut_rod(prices, n)
|
|
# best_price = bottom_up_cut_rod(prices, n)
|
|
# best_price = simple_cut_rod(prices, n)
|
|
elapsed = time.perf_counter() - start
|
|
|
|
print(f"Best Revenue is upto : {best_price}")
|
|
print(f"Time Elapsed : {elapsed:.9f}s")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|