排序后背包

排序后进行背包 DP

一、例题：烹调方案

有 $n$ 份食材，第 $i$ 份需要 $c_i$ 单位时间烹调。如果它在时刻 $t$ 完成，得到的美味指数为 $a_i-b_i t$ 。每份食材最多烹调一次，同时只能烹调一份，要求在时刻 $T$ 前完成，求最大美味指数之和。

不同于普通 01 背包，食材的贡献与完成时刻有关，因此选择的顺序也会影响答案。先确定一个合适的顺序，再用背包决定每份食材选或不选。

二、交换相邻食材，确定顺序

假设两份相邻的食材 $i,j$ 开始烹调前已经经过 $s$ 单位时间。

先做 $i$ 再做 $j$ ，两者的美味指数之和为：

a_i-b_i(s+c_i)+a_j-b_j(s+c_i+c_j).

先做 $j$ 再做 $i$ ，两者的美味指数之和为：

a_j-b_j(s+c_j)+a_i-b_i(s+c_j+c_i).

两式相减可知，先做 $i$ 不差于先做 $j$ 当且仅当：

b_i c_j\ge b_j c_i.

因此按这个条件排序。相等时两种顺序的贡献相同。交换相邻食材不改变两者的总耗时，也不影响后面食材的完成时刻，所以对任意选出的食材，都可以调整为这个排序顺序而不使答案变差。

排序使用交叉相乘，避免除法和精度问题，也能处理 $b_i=0$ 。比较时使用 long long。

三、排序后做 01 背包

设 dp[t] 表示处理过的食材中，恰好用去 $t$ 单位时间时的最大美味指数。

初始化 dp[0]=0，其他状态设为负无穷。若在时刻 $t$ 完成当前食材，它带来的美味指数为 $a_i-b_i t$ ：

$$dp[t]=\max\bigl(dp[t],\ dp[t-c_i]+a_i-b_i t\bigr).$$

转移来源必须可达。时间倒序枚举，保证每份食材最多选一次。由于不必用完全部时间，答案是 $\max_{0\le t\le T}dp[t]$ 。

这里使用恰好用时的状态，是为了让 $t$ 与当前食材的实际完成时刻一致。 $b_i\ge0$ ，空闲等待不会提高美味指数，因此只需考虑从时刻 $0$ 开始连续烹调的方案。

四、参考代码

下面的输入格式与原题相同：先输入 $T,n$ ，再分别输入 $a$ 、 $b$ 、 $c$ 三行。本课程配套题明确约定 $n\le50$ 、 $T\le99999$ 、 $0\le a_i,b_i\le99999$ 、 $1\le c_i\le99999$ 。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 55;
const int MAX_T = 100005;
const long long NEG = -(1LL << 60);
struct Food { long long a, b, c; } food[N];
long long dp[MAX_T];

bool cmp(const Food &x, const Food &y) {
    return x.c * y.b < y.c * x.b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, n;
    cin >> T >> n;
    for (int i = 1; i <= n; ++i) cin >> food[i].a;
    for (int i = 1; i <= n; ++i) cin >> food[i].b;
    for (int i = 1; i <= n; ++i) cin >> food[i].c;
    sort(food + 1, food + n + 1, cmp);
    fill(dp, dp + T + 1, NEG);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int t = T; t >= food[i].c; --t) {
            if (dp[t - food[i].c] != NEG) {
                dp[t] = max(dp[t], dp[t - food[i].c] + food[i].a - food[i].b * t);
            }
        }
    }
    cout << *max_element(dp, dp + T + 1) << '\n';
}

排序的时间复杂度为 $O(n\log n)$ ，背包的时间复杂度为 $O(nT)$ ，总空间复杂度为 $O(n+T)$ 。