货物调度

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

按仓库取价值最高的前 k 件货物，将每个仓库视为多重选择组，再以总费用为容量做背包。

OJ: shumeng

题目 ID: CSP202406D

难度:提高+/省选-

标签:背包分组背包排序

日期: 2026-07-31 16:21

形式化题目

有 $n$ 个仓库，仓库 $j$ 卖出货物要支付基本运费 $b_j$ 和每件 $c_j$ 的计件运费；仓库中放有若干货物，每件价值 $a_i$ 。可以选择卖任意数量的货物，只要某仓库卖 $k$ 件，就要付 $b_j + k c_j$ 。

求满足“卖出的货物总价值 - 总费用 $\ge v$ ”的前提下，最小的总费用。

思路

先观察一个简化事实：同一仓库决定卖 $k$ 件时，计件费用固定，为了净现金最大应取价值最高的 $k$ 件。于是每个仓库的决策从“选哪些货物”压缩成“选前 $k$ 件”，问题变成分组背包。

朴素做法：01 序列枚举每件货物

先看最直接的做法，用 01 选择序列枚举每件货物卖或不卖，到叶子节点统一检查方案是否满足目标。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * 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:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，用 01 选择序列枚举每件货物卖或不卖，只适合 m 很小的数据。
#include <bits/stdc++.h>
using namespace std;

int n, m, target;
vector<int> basic_cost, piece_cost, value, warehouse;
vector<int> choose_item; // choose_item[i] 表示第 i 件货物：0 不卖，1 卖
int answer;

// 检查当前完整的 01 选择序列对应的方案是否满足目标
void check_choice() {
    vector<int> count(n, 0);
    vector<int> total_value(n, 0);
    for (int i = 0; i < m; i++) {
        if (choose_item[i] == 0) continue;
        count[warehouse[i]]++;
        total_value[warehouse[i]] += value[i];
    }
    int profit = 0;
    int cost = 0;
    for (int i = 0; i < n; i++) {
        if (count[i] == 0) continue;
        cost += basic_cost[i] + count[i] * piece_cost[i];
        profit += total_value[i] - basic_cost[i] - count[i] * piece_cost[i];
    }
    if (profit >= target) answer = min(answer, cost);
}

// 第 index 件货物只有卖/不卖两种选择
void enumerate_choice(int index) {
    if (index == m) {
        check_choice();
        return;
    }
    choose_item[index] = 0;
    enumerate_choice(index + 1);
    choose_item[index] = 1;
    enumerate_choice(index + 1);
}

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

    cin >> n >> m >> target;
    basic_cost.resize(n);
    piece_cost.resize(n);
    for (int i = 0; i < n; i++) cin >> basic_cost[i] >> piece_cost[i];
    value.resize(m);
    warehouse.resize(m);
    for (int i = 0; i < m; i++) cin >> value[i] >> warehouse[i];

    choose_item.assign(m, 0);
    answer = 1000000000;
    enumerate_choice(0);
    cout << answer << '\n';
    return 0;
}

枚举所有 $2^m$ 个子集， $m$ 稍大就不可行，只适合小数据验证。

主解：分组背包

对每个仓库，把货物价值降序排序。若该仓库选前 $k$ 件，费用为

cost = b_j + k \cdot c_j,

净现金为前 $k$ 件价值之和减去这个费用。于是一个仓库产生 $k = 1 \dots \text{仓库货物数}$ 个“费用—收益”互斥选项。

设 dp[c] 表示已经处理完若干仓库、恰好花费 $c$ 时能获得的最大净现金。处理每个仓库时，先复制一份旧 dp 表示“不选该仓库”，再枚举选择前 $k$ 件的每个选项，从旧 dp 转移。同一仓库的不同选项互斥，所以必须从旧状态转移而不是滚动覆盖。

费用上界

由于 $b_j, c_j \le 20$ ，全部货物都卖出时的总费用不超过

20n + 20m \le 40000,

可以按费用开数组，最后扫描满足 dp[c] >= v 的最小 $c$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * 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:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXC = 40005;

int n, m, target;
int basic_cost[MAXN];   // 仓库 i 的基本运费
int piece_cost[MAXN];   // 仓库 i 每件货物的计件运费
vector<int> goods[MAXN]; // goods[i] 存放仓库 i 中所有货物的价值
int dp[MAXC];    // dp[c] 表示恰好花费 c 时能获得的最大净现金
int next_dp[MAXC]; // 处理当前仓库时的滚动数组

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

    cin >> n >> m >> target;
    for (int i = 0; i < n; i++) cin >> basic_cost[i] >> piece_cost[i];
    for (int i = 0; i < m; i++) {
        int value, warehouse;
        cin >> value >> warehouse;
        goods[warehouse].push_back(value);
    }

    // 同一仓库选 k 件时应取价值最高的 k 件，先降序排序；同时算出最大可能花费
    int maximum_cost = 0;
    for (int i = 0; i < n; i++) {
        if (goods[i].empty()) continue;
        sort(goods[i].begin(), goods[i].end(), greater<int>());
        maximum_cost += basic_cost[i] + piece_cost[i] * (int)goods[i].size();
    }

    // 分组背包：把每个仓库看作一组，组内选项是“选前 k 件”的所有 k
    const int NEG_INF = -1000000000;
    for (int c = 0; c <= maximum_cost; c++) dp[c] = NEG_INF;
    dp[0] = 0;

    for (int warehouse = 0; warehouse < n; warehouse++) {
        if (goods[warehouse].empty()) continue;
        // next_dp 先复制 dp，表示“不选这个仓库”的情况
        for (int c = 0; c <= maximum_cost; c++) next_dp[c] = dp[c];

        int profit = -basic_cost[warehouse];
        for (int count = 1; count <= (int)goods[warehouse].size(); count++) {
            profit += goods[warehouse][count - 1] - piece_cost[warehouse]; // 选前 count 件的净现金
            int cost = basic_cost[warehouse] + count * piece_cost[warehouse];
            // 从旧 dp 转移，保证同一仓库的不同选项互斥
            for (int old_cost = 0; old_cost + cost <= maximum_cost; old_cost++) {
                if (dp[old_cost] == NEG_INF) continue;
                if (next_dp[old_cost + cost] < dp[old_cost] + profit) {
                    next_dp[old_cost + cost] = dp[old_cost] + profit;
                }
            }
        }
        for (int c = 0; c <= maximum_cost; c++) dp[c] = next_dp[c];
    }

    // 找满足净现金 >= target 的最小花费
    int answer = maximum_cost;
    for (int c = 0; c <= maximum_cost; c++) {
        if (dp[c] >= target && c < answer) answer = c;
    }
    cout << answer << '\n';

    return 0;
}

复杂度

设货物总数 $m$ 、最大费用 $C \le 40000$ 。

时间：每个仓库的选项总数为 $O(n + m)$ ，分组转移 $O(C(n + m))$ ，排序 $O(m \log m)$ 。
空间：DP 数组 $O(C)$ ，货物存储 $O(m)$ 。

总结

把“同仓库选哪些货物”先压缩为“选前 $k$ 件”，再用费用上界做分组背包，就把指数级子集选择变成了可控的费用 DP。分组背包的要点是同一组内选项互斥，转移必须基于处理该组之前的旧状态。

题目来自第 34 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

西西艾弗岛上共有 $n$ 间物流仓库，小 P 目前有 $m$ 件货物存放其中。为了获得至少为 $v$ 的现金，小 P 需要选取一些货物卖出。

已知货物信息如下，第 $i$ 件（ $0 \le i < m$ ）货物：

存放在第 $t_i$ 间仓库中（ $0 \le t_i < n$ ）；
价值为 $a_i$ ，即选择卖出该货物可获得 $a_i$ 的现金。

但在调货出库时也需要支付一些费用，对于第 $j$ 间（ $0 \le j < n$ ）仓库：

只要调用了该仓库的货物（至少一件），就需要支付 $b_j$ 的基本费用；
如果调用了该仓库中共 $k$ 件货物，则还需要支付 $k \times c_j$ 的计件费用。

小 P 的最终目标是获得至少为 $v$ 的现金，即要求卖出的货物总价值减去总费用的结果大于或等于 $v$ 。在满足该目标的前提下，试为小 P 规划一种花费最小的卖货方案。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n,m,v$ 。

接下来 $n$ 行输入仓库信息，其中第 $j$ 行（ $0 \le j < n$ ）包含两个整数 $b_j$ 和 $c_j$ 。

接下来 $m$ 行输入货物信息，其中第 $i$ 行（ $0 \le i < m$ ）包含两个整数 $a_i$ 和 $t_i$ 。

输出格式

输出到标准输出。

仅输出一个整数，表示完成目标前提下的最小花费。

input1

output1

样例 1 解释

最优方案：选取货物 $0$ 和 $2$ ，二者均在 $0$ 号仓库，总花费为 $2 + 2 \times 1 = 4$ 。

选取货物 $1$ 也刚好能满足要求（ $20 - 3 - 1 \times 2 \ge 15$ ），但花费更多。

单独选取货物 $0$ 或 $2$ 均不能满足要求。

input2

output2

样例 2 解释

小 P 所有货物均存放在仓库 $1$ 中，任取两件货物卖出即可满足要求（ $10 + 10 - 1 - 2 \times 1 \ge 15$ ）。

子任务

$30\%$ 的数据满足 $m \le 15$ ；

另有 $40\%$ 的数据满足 $a_i \le 20$ ；

全部的数据满足：

$0 < n, m \le 1000$
$0 < b_j, c_j \le 20$
$0 < a_i \le 1000$
$0 < v \le 10^{6}$ 且保证至少存在一种可满足要求的卖货方案。

货物调度

目录

形式化题目

思路

朴素做法：01 序列枚举每件货物

主解：分组背包

费用上界

代码

复杂度

总结