小编点评

**博客地址：** https://www.cnblogs.com/zylyehuo/# -*- coding: utf-8 -*- **代码：** ```python import timedef def cal_time(func): def wrapper(*args, **kwargs): t1 = time.time() result = func(*args, **kwargs) t2 = time.time() print("%s running time: %s secs.\" % (func.__name__, t2 - t1), end='--------------------') return result return wrapper def cut_rod_recurision_1(p, n): if n == 0: return 0 else: res = p[n] for i in range(1, n): res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i)) return res def cut_rod_recurision_2(p, n): if n == 0: return 0 else: res = 0 for i in range(1, n + 1): res = max(res, p[i] + cut_rod_recurision_2(p, n - i)) return res def cut_rod_dp(p, n): r = [0] for i in range(1, n + 1): res = 0 for j in range(1, i + 1): res = max(res, p[j] + r[i - j]) r.append(res) return r[n] def cut_rod_extend(p, n): r = [0] s = [0] for i in range(1, n + 1): res_r = 0 res_s = 0 for j in range(1, i + 1): if p[j] + r[i - j] > res_r: res_r = p[j] + r[i - j] res_s = j r.append(res_r) s.append(res_s) return r[n], sprint("=================================重构解=================================\")r, s def cut_rod_solution(p, n): r, s = cut_rod_extend(p, n) ans = [] while n > 0: ans.append(s[n]) n -= s[n] return ans ``` **运行结果：** ``` 0 running time: 0 secs. =================================================重构解================================= [20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40] ================================按如下切割============================== [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] ``` **总结：** 该代码展示了递归解剪带问题的几种实现方法，并使用 `timedef` 模块记录运行时间。

正文

博客地址：https://www.cnblogs.com/zylyehuo/

• 
• 
• 
• 
• 
• 
• 
• 
• 

# -*- coding: utf-8 -*-

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        t1 = time.time()
        result = func(*args, **kwargs)
        t2 = time.time()
        print("%s running time: %s secs." % (func.__name__, t2 - t1), end='--------------------')
        return result

    return wrapper


p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]


# p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

# 递归--计算效率低
def cut_rod_recurision_1(p, n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1, n):
            res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i))
        return res


@cal_time
def c1(p, n):
    return cut_rod_recurision_1(p, n)


def cut_rod_recurision_2(p, n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1, n + 1):
            res = max(res, p[i] + cut_rod_recurision_2(p, n - i))
        return res


@cal_time
def c2(p, n):
    return cut_rod_recurision_2(p, n)


print(c1(p, 15))
print(c2(p, 15))


# 自底向上实现
@cal_time
def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n + 1):
        res = 0
        for j in range(1, i + 1):
            res = max(res, p[j] + r[i - j])
        r.append(res)
    return r[n]


print(cut_rod_dp(p, 15))


# 重构解
def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n + 1):
        res_r = 0  # 价格的最大值
        res_s = 0  # 价格最大值对应方案的左边不切割部分的长度
        for j in range(1, i + 1):
            if p[j] + r[i - j] > res_r:
                res_r = p[j] + r[i - j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s


print("=================================重构解=================================")
r, s = cut_rod_extend(p, 20)
print(s)


# 切割方案
def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans


print("================================按如下切割===============================")
print(cut_rod_solution(p, 20))