动态规划0-1背包问题

Hope ·

更新时间:2024-09-21

· 780 次阅读

动态规划通常应用于最优化问题，即要做出一组选择以达到一个最优解。在做选择的同时，经常出现同样形式的问题。当某一特定的子问题可能出自于多于一种选择的集合时，动态规划是很有效的；关键技术是存储这些子问题每一个的解，以备它重复出现。

问题描述

有N件物品和一个容量为V的背包。第i件物品的价值是c[i]，重量是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。每种物品只有一件，可以选择放或者不放。

问题分析

设变量V[i, j]表示在背包容量为j的前提下，装前i个物品的最大价值。
那么针对V[i,j]我们先考虑第5件物品要不要装，有两种情况：第5件物品的重量大于背包的容量 w[i]>j和第5件物品的重量小于等于背包容量 w[i]<=j。而第二种情况又可以分为两种情况：装和不装，那么我们肯定选择其中一种使得V[i,j]最优。

下面探索求解公式：

w[i]>j：
第i件物品无法装配，那么容量j不变，价值不变，下面需要从前i-1件物品里求解，那么该种情况下原问题就变成了V[i,j]=V[i-1,j]

w[i]<=j 装：
装下第i件商品，容量减少w[i]，但是价值增加了v[i]，再向上求解就变成了V[i-1,j-w[i]]，此时V[i,j]=V[i-1,j-w[i]]+v[i]
w[i]<=j 不装：
容量价值都没有变化，但是再向上求解是从i-1件物品中，此时V[i,j]=V[i-1,j]
从装与不装中选择最大值，即是V[i,j]=max{V[i-1,j-w[i]]+v[i], V[i-1,j]}

总结出V[i,j]的递归求解公式为：

我们发现，原问题分解的子问题也都是子问题的最优解，所以满足最优子结构性质。
对于每个子问题的解，我们使用二维数组表示，解决了重复计算重叠子问题的问题。

代码实现

def find(a,b,V,w,v):
    items = list()
    def findItem(i,j):  # 回溯找到装入的物品
        if i>0:
            if V[i][j]==V[i-1][j]:  # 第i个物品没有装,包括w[i]>j和能装但是没装这两种情况
                findItem(i-1,j)     # 那么回溯到i-1个物品
            elif (w[i]j:
                V[i][j] = V[i-1][j]
            else:
                V[i][j] = max(V[i-1][j], V[i-1][j-w[i]]+v[i])
    print('\n',V)
    # 回溯寻找装入物品的序号
    print('装入的物品序号为：',find(N,C,V,w,v)[::-1])
main()

作者：@小楫夜泊

动态规划背包问题动态

1024 个赞