思路与算法

工作i先付D_i再收回C_i，总资金减少D_i-C_i>0。按C_i从大到小排序；dp[b]表示剩余b元最多已做多少项，初始仅dp[M]=0。每项按b从小到大扫描，若b≥D_i，用dp[b]+1更新dp[b-D_i+C_i]。最后取最大值。

正确性说明

若C_i≥C_j，先做j再做i所需资金为max(D_j,D_j-C_j+D_i)，它既不小于D_i，也不小于D_i-C_i+D_j，故交换成i先j后不增加初始资金要求。任何可行子集因此能按此顺序完成。DP逐项包含选与不选两类；目标资金严格更小且已经扫描过，所以本项不会重复使用。按项归纳得每种剩余资金的最优项数，取最大即全局答案。

复杂度

O(N log N+NM)时间、O(N+M)空间，包含作业排序和M+1个状态初始化。

易错点

收益C_i不是净收入，资金会严格减少；必须付得起D_i。这里扫描剩余资金升序，不能套用另一种容量定义的倒序模板。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, M;
    cin >> n >> M;
    vector<pair<int, int>> a(n);
    for (auto &x : a)
        cin >> x.second;
    for (auto &x : a)
        cin >> x.first;
    sort(a.rbegin(), a.rend());
    vector<int> d(M + 1, -1000000);
    d[M] = 0;
    for (auto x : a) {
        int C = x.first, D = x.second, loss = D - C;
        for (int money = D; money <= M; money++)
            if (d[money] >= 0)
                d[money - loss] = max(d[money - loss], d[money] + 1);
    }
    cout << *max_element(d.begin(), d.end()) << "\n";
}