背包DP的学习

目前需要掌握的背包DP主要包括以下几种：

• 01背包
• 恰好装满的01背包
• 完全背包

一、01背包

P1048 [NOIP 2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例 #1

输入 #1

70 3
71 100
69 1
1 2

输出 #1

3

说明/提示

【数据范围】

• 对于 $30\%$ 的数据，$M \le 10$；
• 对于全部的数据，$M \le 100$。

【题目来源】

NOIP 2005 普及组第三题

解决方案

一颗草药一旦被采摘就会消失，所以这里显然是一个01背包问题。

import sys

def main():
    t, m = map(int, input().split())

    times, values =[], []
    for _ in range(m):
        time, value = map(int, sys.stdin.readline().strip().split())
        times.append(time)
        values.append(value)

    times.insert(0, 0)
    values.insert(0, 0)

    # 创建背包dp数组
    # dp[i][j]的含义为在只放前i个物品的情况下容量为j的背包里物品的最大价值
    # 在这道题目中t即为背包的容量，m为最多可能放进去的物品个数
    # 因此应该构建一个dp[m][t]
    dp = [[0 for _ in range(t+1)] for __ in range(m+1)]

    # 开始进行dp
    for i in range(1, m+1):
        for j in range(1, t+1):
            # 如果剩余的时间足够采第i颗药
            if j >= times[i]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-times[i]] + values[i])
            # 如果不够
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[m][t])

if __name__ == "__main__":
    main()

Bingo!

P1507 NASA的食物计划

题目背景

NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。

题目描述

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

输入格式

第一行 $2$ 个整数，分别代表体积最大值 $h$ 和质量最大值 $t$。

第二行 $1$ 个整数代表食品总数 $n$。

接下来 $n$ 行每行 $3$ 个数 体积 $h_i$，质量 $t_i$，所含卡路里 $k_i$。

输出格式

一个数，表示所能达到的最大卡路里（int 范围内）

输入输出样例 #1

输入 #1

320 350
4
160 40 120
80 110 240
220 70 310
40 400 220

输出 #1

550

说明/提示

对于 $100\%$ 的数据，$h,t,h_i,t_i \le 400$，$n \le 50$，$k_i \le 500$。

解决方案

题目中已经明确了每个食品只能使用一次，因此这道题是一个01背包问题。但是这道题与上一道不同的地方在于这里相当于有两个背包容量，需要多开一维dp数组。

import sys

def main():
    h, t = map(int, input().split())
    
    n = int(input())

    hh, tt, kk = [], [], []
    for i in range(n):
        hi, ti, ki = map(int, sys.stdin.readline().strip().split())
        hh.append(hi)
        tt.append(ti)
        kk.append(ki)

    hh.insert(0, 0)
    tt.insert(0, 0)
    kk.insert(0, 0)

    # 创建dp[n][h][t]
    dp = [[[0 for _ in range(t+1)] for __ in range(h+1)] for ___ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, h+1):
            for k in range(1, t+1):
                # 如果有容量放第i个食品
                if j >= hh[i] and k >= tt[i]:
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-hh[i]][k-tt[i]] + kk[i])
                # 否则
                else:
                    dp[i][j][k] = dp[i-1][j][k]

    print(dp[n][h][t])


if __name__ == "__main__":
    main()

采用和上题类似的思路顺利AC：

二、恰好装满的01背包

力扣2915.和为目标值的最长子序列的长度

解决方案

不难发现这道题要求子序列的和必须为target，那么这种情况就是必须要将背包完全装满的01背包问题。

而这种情形的解决方案和朴素的01背包的唯一不同就是对DP数组的初始化方式，我们需要使用负无穷来进行初始化：

dp = [[-inf for _ in range(t+1)] for __ in range(c+1)]
for i in range(c+1): dp[i][0] = 0

这样一来，在每次进行状态转移的时候（dp[j - w[i]]），只要最后不能到达dp[i][0] = 0，dp[i][j]就永远会是负无穷，也就是说背包无法完全装满。

根据这个思路我们可以得到以下的解决方案：

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        inf = float('inf')

        weights = nums[:]
        values = [1] * (len(weights)+1)

        c, t = len(weights), target
        weights.insert(0, 0)
        # 创建dp[c][t]
        dp = [[-inf for _ in range(t+1)] for __ in range(c+1)]
        for i in range(c+1): dp[i][0] = 0

        for i in range(1, c+1):
            for j in range(1, t+1):
                if j >= weights[i]:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
                else:
                    dp[i][j] = dp[i-1][j]

我们也可以采用滚动数组的方式解题，这样可以为下面学习完全背包做好准备：

class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        inf = float('inf')

        weights = nums[:]
        values = [1] * (len(weights)+1)

        c, t = len(weights), target
        weights.insert(0, 0)
        # 创建dp[t]
        dp = [-inf for _ in range(t+1)]
        dp[0] = 0

        for i in range(1, c+1):
            for j in range(t, weights[i]-1, -1):
                dp[j] = max(dp[j], dp[j-weights[i]] + values[i])

        if dp[t] >= 0:
            return dp[t]
        else:
            return -1

这个状态转移方程是如何得到的呢？

最开始的状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])

这种情况下，如果我们有一个i*i的表格，那么我们每次进行状态转移都是根据第i-1行的内容在下方的第i行上新增数据。

而如果我们将状态转移方程改写为：

dp[i][j] = max(dp[i][j], dp[i][j-weights[i]] + values[i])

那么此时我们在进行状态转移的时候就是根据第i行的内容在第i行上更改数据。

同时不难发现，这个时候我们只需要考虑j的变化即可，i完全可以省略，即为：

dp[j] = max(dp[j], dp[j-weights[i]] + values[i])

那么这个时候我们原本开辟的二维dp[i][j]数组就被简化为了一个一维的dp[j]数组，空间复杂度得以被大幅简化。

此外我们需要注意的是，在采用滚动数组写法之后内层的嵌套循环由原本的正循环改为了负循环，我们通过一个实例来感受为什么要这么做：

dp[j]	0	1	2	3	4	5

如果我们采用正循环的话，dp数组就会变为（类似前缀和）：

dp[j]	0	1	3	6	10	15

而正确的负循环的情况下，dp数组其实应该是：

dp[j]	0	1	3	5	7	9

不难发现如果要采用正循环的话，在每次进行状态转移的时候前边“已经被放进背包”的物品会被再放进去一遍，这就违背了01背包的定义，所以我们应该采用负循环的写法。但是，正循环造成的重复放置又恰恰满足了完全背包的定义，一个物品得以被最大程度地重复放置，所以在完全背包当中我们将要采用正循环的写法。

三、完全背包

P1616 疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$. 每种草药可以无限制地疯狂采摘。

$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例 #1

输入 #1

70 3
71 100
69 1
1 2

输出 #1

140

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $m \le 10^3$ 。
• 对于 $100\%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。

解决方案

完全背包的模板题，思路不再赘述。

import sys

def main():
    t, m = map(int, input().split())

    times, values = [], []
    for i in range(m):
        time, value = map(int, sys.stdin.readline().strip().split())
        times.append(time)
        values.append(value)

    times.insert(0, 0)
    values.insert(0, 0)

    # 创建dp[t]
    dp = [0 for i in range(t+1)]
    for i in range(1, m+1):
        for j in range(times[i], t+1):
            dp[j] = max(dp[j], dp[j-times[i]]+values[i])

    print(dp[t])

if __name__ == "__main__":
    main()