钢条切割问题python

一、问题描述

某公司出售钢条，出售价格与钢条长度之间的关系如下表：

问题:现有一段长度为n的钢条和上面的价格表，求切割钢条方案，使得总收益最大。

思考过程：

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

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

def cut_rod2(p, n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1, n):
            res = max(res, p[i] + cut_rod2(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_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

def cut_solution(p, n):
    r, s = cut_extend(p ,n)
    ans = []
    while n>0:
        ans.append(s[n])
        n -= s[n]
    return ans

print(cut_rod1(p, 5))
print(cut_rod2(p, 5))
print(cut_rod_dp(p, 5))
print(cut_solution(p, 5))

二、结果展示

13
13
13
[2, 3]

原文地址：https://blog.csdn.net/lebrongao/article/details/143660970

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！