术→技巧, 法→原理, 研发, 算法实现

动态规划之背包问题

钱魏Way · · 2,050 次浏览

背包问题(Knapsack problem)是动态规划的经典问题。动态规划的基础是递归,和分治一样,都是假设子问题已经解决,由子问题的解组合计算得到父问题的解,类似裴波那契数列中的递推式如f(n) = f(n-1) + f(n-2)。但在递归的过程中会出现重复计算子问题的现象,为了避免重复计算,用一个表格记录子问题的结果供查找,从下往上进行递推。找递推式(or 状态转移方程)的思路一般是由最终状态往前回溯,考察解答最终问题需要哪些子问题。

背包问题,有很多中类型,常见的有:

  • 01背包(ZeroOnePack): 有N件物品和一个容量为V的背包,每种物品均只有一件。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
  • 完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
  • 多重背包(MultiplePack): 有N种物品和一个容量为V的背包,第i种物品最多有n[i]件可用。每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

01背包

动态规划的核心过程有两部分,一个是找出问题的“子状态”,再一个就是建立“状态转移方程”(所谓的递推公式)。欲求背包能够获得的总价值,即求前i个物体放入容量为m背包的最大价值c[i][m]

  • w[i]:第i个物体的重量
  • p[i]:第i个物体的价值
  • c[i][j]:前i个物体放入容量为j 包的最大价值
  • c[i-1][j]:前i-1个物体放入容量为j 包的最大价值
  • c[i-1][j-w[i]]:前i-1个物体放入容量为j-w[i] 包的最大价值

以下通过表格来说状态转移方程:

c[i][m]=max{c[i-1][m-w[i]]+p[i],c[i-1][m]}

这里是用二维数组存储的,可以把空间优化,用一维数组存储。 用c[0..m]表示,c[m]表示把前i件物品放入容量为m的背包里得到的价值。把i从1~n(n件)循环后,最后c[m]表示所求最大值。

这里c[m]就相当于二维数组的c[i][m]。那么,如何得到c[i-1][m]和c[i-1][m-w[i]]+p[i]?

首先要知道,我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即:for i=1..N。现在思考如何能在是c[m]表示当前状态是容量为m的背包所得价值,而又使c[m]和c[m-w[i]]+p[i]标签前一状态的价值?

答案是逆转:

for i=1..N
   for m=V..0
        c[m]=max{c[m],c[m-w[i]]+p[i]};

分析上面的代码:当内循环是逆序时,就可以保证后一个c[m]和c[m-w[i]]+p[i]是前一状态的!这里给大家一组测试数据:

相关代码实现:

#A naive recursive implementation of 0-1 Knapsack Problem
 
# Returns the maximum value that can be put in a knapsack of
# capacity W
def knapSack(W , wt , val , n):
 
    # Base Case
    if n == 0 or W == 0 :
        return 0
 
    # If weight of the nth item is more than Knapsack of capacity
    # W, then this item cannot be included in the optimal solution
    if (wt[n-1] > W):
        return knapSack(W , wt , val , n-1)
 
    # return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    else:
        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),
                   knapSack(W , wt , val , n-1))
 
# end of function knapSack
 
# To test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W , wt , val , n))
 
# This code is contributed by Nikhil Kumar Singh.

以上方法的时间和空间复杂度为O(n*W),其中时间复杂度已经不能再优化了,但是空间复杂度可以优化到O(W),优化后的代码如下:

# A Dynamic Programming based Python Program for 0-1 Knapsack problem
# Returns the maximum value that can be put in a knapsack of capacity W
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
 
    # Build table K[][] in bottom up manner
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
 
    return K[n][W]
 
# Driver program to test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
 
# This code is contributed by Bhavya Jain

上述代码实现为01背包问题的实现原理,如需在实际情况中采用类似的思路解决问题,可以使用Google Optimization Tools工具,具体代码如下:

 

from ortools.algorithms import pywrapknapsack_solver

weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
            125, 670, 892, 600, 293, 712, 147, 421, 255]]
capacities = [850]
values = weights[0]

# Create the solver.
solver = pywrapknapsack_solver.KnapsackSolver(pywrapknapsack_solver.KnapsackSolver.KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
                                              'test')

solver.Init(values, weights, capacities)
computed_value = solver.Solve()

packed_items = [x for x in range(0, len(weights[0]))
                if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]

print("Packed items: ", packed_items)
print("Packed weights: ", packed_weights)
print("Total weight (same as total value): ", computed_value)

参考链接:

完全背包

完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的重量为w [i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。完全背包按其思路仍然可以用一个二维数组来写出:

c[i][m] = max{c[i-1][m-k*c[i]] + k*p[i] | 0<=k*c[i]<=m }

同样可以转换成一维数组来表示:

for i=1..N
    for m=0..V
        c[m]=max{c[m],c[m-w[i]]+p[i]}

完全和01背包的区别,这里的内循环是顺序的,而01背包是逆序的。为何完全背包可以这么写?原因是为了max中的两项是前一状态值。那么这里,我们顺序写,这里的max中的两项当然就是当前状态的值了,为何? 因为每种背包都是无限的。当我们把i从1到N循环时,c[m]表示容量为m在前i种背包时所得的价值,这里我们要添加的不是前一个背包,而是当前背包。所以我们要考虑的当然是当前状态。

参考链接:

多重背包

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件重量是w[i],价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则有状态转移方程:

c[i][m]=max{c[i-1][m-k*w[i]]+k*p[i]|0<=k<=n[i]}

其他参考:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注