动态规划

我们先来看著名的背包问题

01背包问题

有n件物品和一个容量为c的背包。（每种物品均只有一件）第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。故称01背包问题。

首先我们得找到问题的状态方程：

假设 dp[i][j] 表示 前 i 件物品恰好放入一个容量为 j 的背包可以获得的最大价值。

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])

代码实现

• Python

def pack01(w,v,c):
    n = len(w)
    ### 注意我们这里i,j从 1 开始. dp[1][1]表示前1件物品容量为1的最大价值。
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,c+1):
            if j>=w[i-1]:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[-1][-1]
w = [2,3,4,5]
v = [3,4,5,6]
c = 8
print(pack01(w,v,c))

完全背包问题

有n种物品和一个容量为c的背包，每种物品都有无限件可用。第i种物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

找到状态方程：

dp[i][j] = max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i]) 其中 k=1,2,3...

我们可以合并dp[i-1][j]，dp[i-1][j-k*w[i]]+k*v[i] 得

dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]) 其中 k=0,1,2...

代码实现

• Python

def back_complete(w,v,c):
    n = len(w)
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,c+1):
            k = 0
            while j>=k*w[i-1]:
                dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i-1]]+k*v[i-1])
                k += 1
    return dp[-1][-1]
w = [2,3,4,5]
v = [3,4,5,6]
c = 8
print(back_complete(w,v,c))

多重背包问题

有n种物品和一个容量为c的背包。第i种物品最多有kk[i]件可用，每件重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

状态方程：

dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]) 其中 k=0,1,2... 且k<=kk[i]

代码实现

• Python

def back_multi(w,v,c,kk):
    n = len(w)
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,c+1):
            k = 0
            while j>=k*w[i-1] and k<=kk[i-1]:
                dp[i][j] = max(dp[i][j],dp[i-1][j-k*w[i-1]]+k*v[i-1])
                k += 1
    return dp[-1][-1]
w = [3,4,5]
v = [4,5,6]
kk = [1,1,1]
c = 10
print(back_multi(w,v,c,kk))