机器人项目管理

GitHub跳转原题关系图Canvas 关系图返回列表

灵活任务按单位咖啡收益率排序，普通任务用 0/1 背包选择，再合并两类任务的最大收益。

OJ: shumeng

题目 ID: CSP202603B

难度:未知

标签:背包0/1 背包贪心排序动态规划

日期: 2026-07-31 16:22

目录

  1. 形式化题目
  2. 思路
    1. 灵活任务：按单位收益贪心
    2. 普通任务：0/1 背包
    3. 合并两类任务
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

有 nn 项任务，每项初始耗时 tit_i。每项任务最多喝 aia_i 杯咖啡，可把耗时减少 bib_i（最终耗时 ti−bi>0t_i-b_i>0）。总咖啡不超过 mm 杯。

  • 灵活型任务：咖啡杯数可在 [0,ai][0,a_i] 内取任意实数，收益随杯数线性变化；
  • 普通型任务：只能选择 00 杯或 aia_i 杯，只有满加速与不加速两种选择。

求最小化的总耗时 ∑iti−最大总减少量\sum_i t_i - \text{最大总减少量}。

思路

总耗时等于初始总耗时减去所有加速带来的减少量，所以问题等价于：在不超过 mm 杯咖啡的限制下，最大化总减少量。

灵活任务：按单位收益贪心

给灵活任务 kiaik_i a_i 杯咖啡可减少 kibik_i b_i 耗时，因此每杯咖啡的收益恒为 bi/aib_i/a_i，与分几杯无关。固定给灵活任务 xx 杯时，按 bi/aib_i/a_i 从大到小依次装满即可得到最大收益，记作 flexible_gain[x]。

普通任务：0/1 背包

普通任务只能整件选择，设 dp[u] 为用恰好 uu 杯咖啡从普通任务获得的最大减少量，这是标准的 0/1 背包转移。

合并两类任务

枚举普通任务用掉的杯数 uu，把剩下的 m−um-u 杯交给灵活任务，取

max⁡u (dp[u]+flexible_gain[m−u]).\max_{u}\ \left(dp[u] + \text{flexible\_gain}[m-u]\right).

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 灵活型任务：咖啡可以取 [0, a] 内任意实数，每杯收益恒为 b/a。
struct FlexibleTask {
    int cups;              // 最多可提供的咖啡杯数 a
    long double gain_per_cup; // 每杯咖啡减少的耗时 b/a
};

// 普通型任务：只能选择 0 杯或 a 杯，只能整件加速。
struct OrdinaryTask {
    int cups;   // 完整加速需要消耗的咖啡杯数 a
    int gain;   // 完整加速减少的耗时 b
};

// 灵活任务按单位咖啡收益从大到小排序，保证贪心填充最优。
bool compare_flexible(const FlexibleTask &x, const FlexibleTask &y) {
    return x.gain_per_cup > y.gain_per_cup;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    long double initial = 0; // 不做任何加速时的总耗时
    vector<FlexibleTask> flexible;
    vector<OrdinaryTask> ordinary;
    for (int i = 0; i < n; i++) {
        int type, t, a, b;
        cin >> type >> t >> a >> b;
        initial += t;
        if (type == 0) {
            FlexibleTask task;
            task.cups = a;
            task.gain_per_cup = (long double)b / a;
            flexible.push_back(task);
        } else {
            OrdinaryTask task;
            task.cups = a;
            task.gain = b;
            ordinary.push_back(task);
        }
    }

    // flexible_gain[c]：把恰好 c 杯咖啡全部分给灵活任务时的最大总减少量。
    // 因为每杯收益固定，从收益率最高的任务开始依次装满即可。
    sort(flexible.begin(), flexible.end(), compare_flexible);
    vector<long double> flexible_gain(m + 1, 0);
    for (int capacity = 0; capacity <= m; capacity++) {
        int left = capacity;
        for (int i = 0; i < (int)flexible.size(); i++) {
            int used = min(left, flexible[i].cups);
            flexible_gain[capacity] += used * flexible[i].gain_per_cup;
            left -= used;
            if (left == 0) break;
        }
    }

    // dp[used]：用恰好 used 杯咖啡从普通任务中获得的最大总减少量。
    // 普通任务只能整件选择，等价于 0/1 背包。
    const long double NEGATIVE = -1e100L;
    vector<long double> dp(m + 1, NEGATIVE);
    dp[0] = 0;
    for (int i = 0; i < (int)ordinary.size(); i++) {
        for (int used = m; used >= ordinary[i].cups; used--) {
            if (dp[used - ordinary[i].cups] > NEGATIVE / 2) {
                dp[used] = max(dp[used],
                    dp[used - ordinary[i].cups] + ordinary[i].gain);
            }
        }
    }

    // 枚举普通任务用掉 used 杯，剩下的 m-used 杯交给灵活任务。
    long double best_gain = 0;
    for (int used = 0; used <= m; used++) {
        if (dp[used] > NEGATIVE / 2) {
            best_gain = max(best_gain, dp[used] + flexible_gain[m - used]);
        }
    }
    cout << fixed << setprecision(6) << initial - best_gain << '\n';
    return 0;
}

复杂度

  • 时间：灵活收益表与普通背包均为 O(nm)O(nm)，总时间复杂度 O(nm)O(nm)。
  • 空间：只需保存两张长度为 mm 的表，空间复杂度 O(m)O(m)。

总结

连续可分配的资源先按单位收益贪心处理；只能整件选择的物品再用背包处理，最后枚举两类资源之间的分配。两类任务收益单位不一致是本题最容易混淆的地方，分开建模后合并即可。