1 题目描述

某公司有一批货物，系了2个轮船进行运输。每条轮船上可以运输不同容量的货物。由于2个轮船的发船时间不一样，同一个货物通过不同的轮船运输到终点后，利润也是不一样的，现在需要根据不同轮船的容量、货物的容量以及在不同轮船上进行运输的利润有效地分配货物，从而达到货物价值最大化。每个货物只有1件。
输入：
第一行输入为A B M，A代表轮船A的容量，B代表轮船B的容量，M代表货物的个数。
之后M行分别代表每个货物的容量、使用轮船A运输的利润、使用轮船B运输的利润。
输出：
最大利润。
例子：
输入：
5 6 4
4 3 2
3 1 4
2 2 4
2 3 3
输出：11
解释：轮船A运输货物1或者4，利润3；轮船B运输货物2和3，利润8；所以最大的利润是11。

2 思路

第一眼看到这个题目大家肯定都会想到0-1背包。的确，这题也是类似的。区别是我们现在有两个背包了。没关系，我们按照步骤一步步分析。

1. 确定dp数组及其下标含义
   回忆一下只有一个背包的情况，dp数组是这样表示的：dp[i][j] 表示当背包容量为j，可选物品下标为0到i时的最大价值。那现在有两个背包，二维数组肯定无法表示全面了，我们需要用到三维。即dp[i][j][k]表示在A船容量为i，B船容量为j，可选货物下标在0到k之间时的最大价值。
2. 确定递推公式
   这个就简单了。在只有一个背包时，对每个物品，我们需要考虑取或者不取两种情况。而现在我们需要考虑的是三种情况，对于某个货物，要么放进A船、要么放进B船、要么哪个都不放。
   则递推公式如下：

dp[i][j][k] = max(dp[i][j][k-1],
                  dp[i - weight][j][k - 1] + value_A,
                  dp[i][j - weight][k - 1] + value_B)

weight是当前货物的容量，value_A、value_B分别表示将第k个货物放进A、B两艘货船产生的价值。两艘船都不放的价值是dp[i][j][k-1]，相当于不考虑第k个货物，只从下标为0到k-1之间的货物里选择；选A船的价值是dp[i - weight][j][k - 1]+ value_A，因为用掉了weight的容量，总价值增加了value_A；选B船的价值是dp[i][j - weight][k - 1] + value_B)，原因同理。
还要注意一点，这个递推公式成立的前提是货船的容量是充足的，实际还要做一个判断。代码如下：

if i >= weight and j >= weight:
    dp[i][j][k] = max(dp[i][j][k-1],
                      dp[i - weight][j][k - 1] + value_A,
                      dp[i][j - weight][k - 1] + value_B)
elif i >= weight:
    dp[i][j][k] = max(dp[i][j][k-1],
                      dp[i - weight][j][k - 1] + value_A)
elif j >= weight:
    dp[i][j][k] = max(dp[i][j][k-1],
                      dp[i][j - weight][k - 1] + value_B)
else:
    dp[i][j][k] = dp[i][j][k - 1]

3. 初始化
   由于递推公式里dp的下标有k-1，所以我们需要对k=0时的情况做初始化，也就是初始化dp[i][j][0]，具体含义为在A船容量为i，B船容量为j，只考虑首个货物时的最大价值。
   这个思路也很简单，直接考虑将第一个货物放在哪艘船价值更大就好了。同样，也要考虑放不放得下的问题。代码如下：

weight, value_A, value_B = matrix[0]
for i in range(1, A + 1):
    for j in range(1, B + 1):     
        if i >= weight and j >= weight:
            dp[i][j][0] = max(value_A, value_B)
        if i >= weight:
            dp[i][j][0] = value_A
        if j >= weight:
            dp[i][j][0] = value_B

4. 确定遍历顺序
   三重循环，从上到下，从左到右即可。

3 完整代码

A, B, M = list(map(int, input().split()))
matrix = []
for _ in range(M):
    matrix.append(list(map(int, input().split())))
dp = [[[0] * (M) for _ in range(B + 1)] for _ in range(A + 1)]
#dp[i][j][k]表示在A船容量为i,B船容量为j,可选货物下标在0到k之间时的最大价值

#初始化
weight, value_A, value_B = matrix[0]
for i in range(1, A + 1):
    for j in range(1, B + 1):     
        if i >= weight and j >= weight:
            dp[i][j][0] = max(value_A, value_B)
        if i >= weight:
            dp[i][j][0] = value_A
        if j >= weight:
            dp[i][j][0] = value_B

for i in range(1, A + 1):
    for j in range(1, B + 1):
        for k in range(1, M):
            weight, value_A, value_B = matrix[k]
            if i >= weight and j >= weight:
                dp[i][j][k] = max(dp[i][j][k-1],
                                  dp[i - weight][j][k - 1] + value_A,
                                  dp[i][j - weight][k - 1] + value_B)
            elif i >= weight:
                dp[i][j][k] = max(dp[i][j][k-1],
                                  dp[i - weight][j][k - 1] + value_A)
            elif j >= weight:
                dp[i][j][k] = max(dp[i][j][k-1],
                                  dp[i][j - weight][k - 1] + value_B)
            else:
                dp[i][j][k] = dp[i][j][k - 1]
print(dp[A][B][M - 1])

运行结果：