1.火车运输

前置知识点：动态规划

1.问题描述

钢厂有一辆用于运送废旧钢材的火车，它具有两节车厢，其中车厢 $1$ 的最大载重量为 $A$，车厢 $2$ 的最大载重量为 $B$。现在一共有 $N$ 件废旧钢材需要被运输，其中第 $i$ 件钢材的重量为 $w_i$。为了最大化运输效率，车长想要一次性运输走重量尽可能多的钢材，请你帮助车长计算出一次运输最多可以带走多大重量的钢材。

每件钢材都是独立的不可分割的，只能被放置在某一节车厢中。在装载钢材时只需要考虑重量条件即可。

2. 输入格式

输入的第一行包含三个整数 $N$，$A$，$B$，用一个空格分隔，分别表示钢材的数目以及两节车厢的最大载重。

第二行包含 $N$ 个整数，分别表示 $w_1$, $w_2$, …, $w_n$，相邻两个整数之间使用一个空格分隔。

3. 输出格式

输出一个整数表示答案。

4. 样例输入

3 10 8
8 9 1

5. 样例输出

18

6. 样例说明

车厢 $1$ 装入第 $2$ 件和第 $3$ 件钢材，车厢 $2$ 装入第 $1$ 件钢材。

7. 评测用例规模与约定

对于 $30\%$ 的评测用例，$1\le N\le 10$；

对于所有评测用例，$1\le N\le 200$，$1\le w_i,A,B\le 1,000$。

8. 原题链接

火车运输

2. 解题思路

这道题目没有直观的解决方案，但我们注意到 $n,A,B$ 的值域都相对较小，因此可以考虑使用动态规划来解决。

首先，我们需要定义状态。令 $f_{i,j,k}$ 表示只考虑前 $i$ 件钢材，使得第一个车厢的载重量严格为 $j$，同时第二个车厢的载重量严格为 $k$ 的情况。

这个状态设计必须能够导出最终的答案。因此，我们可以分别遍历所有可能的 $j$（满足 $j\in [1,A]$）和 $k$（满足 $k\in [1,B]$）。如果 $f_{n,j,k}$ 为真，那么 $j+k$ 就是一个可行的答案。最终的答案即为所有可能的 $(j,k)$ 组合中，$j+k$ 的最大值。

接下来，我们需要初始化状态。在最初，没有任何钢材被放入任何一个车厢，所以我们设定 $f_{0,0,0}$ 为真。

然后，我们来考虑状态转移。对于 $f_{i,j,k}$，当考虑第 $i$ 个钢材时，我们有三种选择：

• 将其放入车厢 $A$（要求 $j\ge a_i$），此时的状态转移方程为：
  $$f_{i,j,k}=f_{i,j,k}\mid f_{i-1,j-a_i,k}$$

• 将其放入车厢 $B$（要求 $k\ge a_i$），此时的状态转移方程为：
  $$f_{i,j,k}=f_{i,j,k}\mid f_{i-1,j,k-a_i}$$

• 不放入任何车厢。

在实现过程中，我们会发现，按照这样的状态设计会导致空间消耗过大。因此，我们可以借鉴 $01$ 背包问题中的滚动数组思想，优化掉第一个维度，并在枚举 $j,k$ 时进行反向枚举。

时间复杂度为：$O(nAB)$。

3. AC_Code

• C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, A, B;
bool f[N][N];
int main()
{
    cin >> n >> A >> B;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    f[0][0] = true;
    for (int i = 0; i < n; ++i)
    {
        for (int j = A; j >= 0; j--)
        {
            for (int k = B; k >= 0; k--)
            {
                if (j >= a[i])
                    f[j][k] |= f[j - a[i]][k];
                if (k >= a[i])
                    f[j][k] |= f[j][k - a[i]];
            }
        }
    }
    int ans = 0;
    for (int j = A; j >= 0; j--)
    {
        for (int k = B; k >= 0; k--)
        {
            if (f[j][k])
                ans = max(ans, j + k);
        }
    }

    cout << ans << '\n';
}

• Java

import java.util.*;

public class Main {
    static final int N = 1010;
    static boolean[][] f = new boolean[N][N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        f[0][0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = A; j >= 0; j--) {
                for (int k = B; k >= 0; k--) {
                    if (j >= a[i])
                        f[j][k] = f[j][k] || f[j - a[i]][k];
                    if (k >= a[i])
                        f[j][k] = f[j][k] || f[j][k - a[i]];
                }
            }
        }

        int ans = 0;
        for (int j = A; j >= 0; j--) {
            for (int k = B; k >= 0; k--) {
                if (f[j][k])
                    ans = Math.max(ans, j + k);
            }
        }

        System.out.println(ans);
    }
}

• Python

N = 1010
f = [[False]*N for _ in range(N)]

n, A, B = map(int, input().split())
a = list(map(int, input().split()))

f[0][0] = True
for i in range(n):
    for j in range(A, -1, -1):
        for k in range(B, -1, -1):
            if j >= a[i]:
                f[j][k] = f[j][k] or f[j - a[i]][k]
            if k >= a[i]:
                f[j][k] = f[j][k] or f[j][k - a[i]]

ans = 0
for j in range(A, -1, -1):
    for k in range(B, -1, -1):
        if f[j][k]:
            ans = max(ans, j + k)

print(ans)