动态规划解决单背包问题

一、问题介绍

单背包问题是指给定一个背包，一些物品，这个背包有承重上限这个属性，而这些物品有重量和价值这两个属性，而这个问题要求解得到的是一个放置物品的策略，要求背包中所放物品的价值总和尽可能的大，但是这个物品的重量总和不能超过背包的承重上限。在之前，我用一些启发式的算法，比如贪心算法、邻居搜索算法和禁忌搜索算法解决过这类问题，在这里我使用了动态规划来解决这个问题。

二、算法

所谓动态规划就是首先将大问题拆分为小问题，而其最关键的是避免了这些小问题的重复解决，而是保留这个小问题的解下一次直接使用。在使用动态规划时，最关键的就是其中的递推公式来得到动态规划表。

在该问题中，我们使用二维的动态规划表来求解，该动态规划表的行表示的是不同的物品，列表示的是不同的背包容量，而填在表中的数值为该种情况下的最大价值。那么我们更新该动态规划表就有两种情况，一种是包的容量比当前的商品体积要小，因此装不下该商品，这时的价值与之前的价值是一样的。第二种情况就是包有足够的容量可以放下该物品，但是装了也不一定能够达到最优的价值，那么我们就要通过比较来决定装或者不装。所以可以得到如下的式子。W,V分别为物品的重量和价值的数组，F表示二维的动态规划表。

$F(i,j) = \left{ \begin{array}{ll} F(i-1,j) & \textrm{j<W(i)}\ max(F(i-1,j),F(i-1,j-W(i))+V(i)) & \textrm{j>=W(i)} \end{array} \right.$

三、代码实现

在具体的代码实现中，我定义了两个函数，分别为FindMax()与FindWhat(),他们分别是为了得到二维动态规划表和得到具体的物品放法。在FindMax函数中，我使用了如上述算法描述的方式更新二维动态规划表，在FindWhat函数中，我从二维动态规划表的末尾处开始遍历二维动态规划表中的内容，返回最优的物品放法。

代码：

#使用动态规划解决单背包问题

#得到具体物品放法
def FindWhat(i,j,dp,V,W,result):
    if i>=0:
        if dp[i][j] == dp[i-1][j]:
             result[i]=0
             FindWhat(i-1,j,dp,V,W,result)
        elif j-W[i]>=0 and dp[i][j] == (dp[i-1][j-W[i]]+V[i]):
             result[i]=1
             FindWhat(i-1,j-W[i],dp,V,W,result)
                
#得到动态规划表
def FindMax(dp,V,W,capacity):
    for i in range(0,len(V)):
        for j in range(0,capacity):
            if j<W[i]:
                dp[i][j]=dp[i-1][j]
            else:
                if dp[i-1][j]>(dp[i-1][j-W[i]]+V[i]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j-W[i]]+V[i]

V=[10, 40, 30, 50]
W=[5, 4, 6, 3]
capacity = 10
number=4
dp=[]
result=[0 for i in range(0,number)]
for i in range(0,number):
    dp.append([])
    for j in range(0,capacity):
        dp[i].append(0)

FindMax(dp,V,W,capacity)
FindWhat(number-1,capacity-1,dp,V,W,result)
print(result)

结果：

1	[0, 1, 0, 1]

四、结论

本文使用了动态规划的方法构造了二维的动态规划表来解决单背包问题，在具体的实现过程中，包括构造和更新二维动态规划表和遍历二维动态规划表返回单背包问题的解法。该解法作为一种最佳化算法而非启发式算法，保证能够得到全局最优解，同时动态规划的分解小问题，求解小问题以及重复利用小问题的解避免了重复求解小问题，提高了解法的性能。