python版本背包问题的动态规划实现

经典背包问题. 背包最多只能容纳固定的空间. 在不同的空间中有几个项目可供选择. 每个项目都有不同的值. 该程序遍历每种可能的组合以选择最佳选择. 解决方案，最大程度地提高了背包中所装物品的价值. 该算法的时间复杂度是指数O（n ^ k）. 使用旧的例程，计算机存储空间可以交换所消耗的时间背包问题 动态规划 python背包问题 动态规划 python，可以有效地提高程序性能并降低时间复杂度:

def fast_knapsack(w, v, i, aw, m):
    global numCalls;
    numCalls += 1
    try:
        return m[(i, aw)]
    except KeyError:
        if i == 0:
            if w[i] < aw:
                return v[i]
            else:
                return 0
        without_i = fast_knapsack(w, v, i - 1, aw, m)
        if w[i] > aw:
            return without_i
        with_i = fast_knapsack(w, v, i - 1, aw - w[i], m) + v[i]
        res = max(without_i, with_i)
        m[(i, aw)] = res
        return res
def knapsack(w, v, i, aW):
    global numCalls
    numCalls += 1
    if i == 0:
        if w[i] <= aW:
            return v[i]
        else:
            return 0
    without_i = knapsack(w, v, i - 1, aW)
    if w[i] > aW:
        return without_i
    else:
        with_i = v[i] + knapsack(w, v, i - 1, aW - w[i])
    return max(with_i, without_i)
if __name__ == '__main__':
    # n = 10
    # w = [2, 6, 5, 4]
    # v = [3, 5, 4, 6]
    # n = 5
    # w = [5,3,2]
    # v = [9,7,8]
    # 
    n = 10
    w = [2, 1, 5, 5, 3, 3, 4, 4]
    v = [15, 15, 10, 10, 9, 9, 5, 5]
    numCalls = 0
    res = knapsack(w, v, len(w) - 1, n)
    print('optimum solution: ', res)
    print('call funstion times: ', numCalls)
    print('')
    numCalls = 0
    res = fast_knapsack(w, v, len(w) - 1, n, {})
    print('optimum solution: ', res)
    print('call funstion times: ', numCalls)

运行结果:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-188265-1.html