RookieSama_

公告

欢迎来到小破站ようこそ私のブログへ！

Learn Morea

标签

2487 字

12 分钟

Bin Packing Problem

2026-01-19

题解

线段树

装箱问题 - 首次适应与最佳适应[[算法]]#

一、核心任务#

实现两种经典的装箱问题近似算法（首次适应算法、最佳适应算法），针对每组输入数据，统计两种算法分别需要使用的箱子总数并输出。

二、题目背景与核心定义#

装箱问题核心#

将不同体积的物品装入固定容量为 C 的箱子中，目标是最小化箱子使用数量（该问题为 NP 难组合优化问题，无多项式时间精确解，需用近似算法）。

物品约束#

每个物品体积 $a_i \leq C$ ，确保单个物品可装入一个箱子。

两个经典近似算法#

算法名称	核心规则
首次适应算法（First Fit）	尝试将当前物品放入箱子列表中第一个能容纳它的箱子，无合适箱子则新增箱子
最佳适应算法（Best Fit）	尝试将当前物品放入能容纳它且剩余空间最小的箱子（最优选择），无合适箱子则新增箱子

箱子剩余空间#

箱子容量 C - 已装入该箱子的所有物品体积之和，判断 “能否容纳” 的依据是「剩余空间 ≥ 物品体积」。

三、输入输出要求#

1. 输入格式#

第一行：正整数 T（测试用例数量）。
每组用例：
- 第一行：两个整数 n（物品数量）、C（箱子固定容量），其中 $1 \leq n \leq 10^6$ ， $1 \leq C \leq 10^9$ 。
- 第二行：n 个整数 $a_i$ （第 i 个物品的体积）， $1 \leq a_i \leq C$ 。

数据约束：所有测试用例的 n 之和不超过 $10^6$ （避免数据量过大超时）。

2. 输出格式#

每组用例输出一行，包含两个整数，依次为首次适应算法（First Fit）、最佳适应算法（Best Fit）的箱子使用数量。

四、样例核心提炼#

输入的 2 组用例对应输出：

2 个体积为 1 的物品，箱子容量 2：两种算法均只需 1 个箱子（输出 1 1）。
5 个物品（5、8、2、5、9），箱子容量 10：首次适应需 4 个箱子，最佳适应需 3 个箱子（输出 4 3），体现最佳适应算法的近似效果更优。

五、解题思路#

1. 首次适应算法（First Fit）#

由于题目的数据过于大，无法直接模拟，需要考虑更高效的算法。
对于区间问题我们能想到 ST 线段树树状数组，但是由于我们需要维护区间最大值，因为 ST 和树状数组不适合修改区间，所以我们需要使用线段树。
时间复杂度为 $O(n \log n)$ (建树 + 查询 + 更新 + 修改)

1
//更新最大值
2
void pushup(Node& u, Node& l, Node& r){
3
    if(l.ma >= r.ma){
4
        u.id = l.id, u.ma = l.ma;
5
    }
6
    else u.id = r.id,u.ma = r.ma;
7
}
8

9
void pushup(int u){
10
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
11
}
12
//建树过程
13
void build(int u,int l, int r){
14
    tr[u].l = l, tr[u].r = r;
15
    if(l == r){
16
        tr[u].ma = 0;
17
        tr[u].id = l;
18
    }
19
    else{
20
        int mid = l + r >> 1;
21
        build(u << 1, l ,mid), build(u << 1 | 1, mid + 1, r);
22
        pushup(u);
23
    }
24
}
25
// 对单点进行修改, 将 x 位置的最大值修改为 v
26
void modify(int u,int x, int v){
27
    if(tr[u].l == x && tr[u].r == x){
28
        tr[u].ma = v;
29
    }
30
    else{
31
        int mid = tr[u].l + tr[u].r >> 1;
32
        if(x <= mid) modify(u << 1, x, v);
33
        else modify(u << 1 | 1, x, v);
34
        pushup(u); //最后往上更新
35
    }
36
}
37
// 查询第一个大于等于 x 的位置 如果在线段树中没有比x大的则直接返回 0
38
int query(int u, int x){
39
    if(tr[u].ma < x) return 0;
40
    if(tr[u].l == tr[u].r){
41
        return tr[u].id;
42
    }
43
    if(tr[u << 1].ma >= x){
44
        return query(u << 1, x);
45
    }
46
    return query(u << 1 | 1, x);
47
}
48
int firstfit(){
49
    build(1, 1, n);//建树 大小为 n
50
    int cnt = 0;
51
    for(int i = 1; i <= n; i++){
52
        int t = query(1, a[i]);
53
        if(t){
54
            b[t] -= a[i]; //b[t] 表示第 t 个箱子的剩余空间
55
            modify(1, t, b[t]);
56
        }
57
        else{
58
            b[++cnt] = m - a[i];
59
            modify(1, cnt, b[cnt]);
60
        }
61
    }
62
    return cnt;
63
}

2. 最佳适应算法（Best Fit）#

由于我们需要维护的是区间最小值，所以我们可以直接使用STL中的multiset 或 priority 来维护。(这里采用 multiset)
因为multiset 是有序的，所以我们可以直接使用 lower_bound 来找到第一个大于等于当前物品体积的箱子。
若找到，则将当前物品放入该箱子中，否则新增一个箱子。最后计算总共的箱子数即可。

1
int Bestfit(){
2
    multiset<int> A; //用于维护箱子的剩余空间，从小到大排序
3
    int cnt = 0;
4
    for(int i = 1; i <= n; i++){
5
        auto it = A.lower_bound(a[i]);//迭代器指向第一个大于等于 a[i] 的位置
6
        if(it != A.end()){ //表示当前存在大于a[i]的值
7
            A.insert(*it - a[i]); //将当前箱子的剩余空间减去 a[i] 后插入到 multiset 中
8
            A.erase(it); //删除当前箱子的剩余空间
9
        }else{
10
            A.insert(C - a[i]); //将当前物品放入新箱子中
11
            cnt++;
12
        }
13
    }
14
    return cnt;
15
}

3. 本题主要收获#

学会如何使用 multiset 的 it迭代器

1
比如： *it 表示当前迭代器指向的位置的值
2
it 表示当前迭代器指向的位置（地址）
3
erase(it) 表示删除当前迭代器指向的位置（注意用的是迭代器删）

简单复习了线段树板子

1
pushup(u); //更新当前节点的最大值
2
build(u, l, r); //建树过程
3
modify(u, x, v); //对单点进行修改, 将 x 位置的最大值修改为 v
4
query(u, x); //查询第一个大于等于 x 的位置

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4
//#define int long long
5
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)  // 加速IO操作
6
#define x first
7
#define y second
8
#define endl "\n"
9
typedef signed long long LL;
10
typedef pair<int, int> PII;
11

12
const int N = 2e6 + 10 , Mod = 998244353, INF = 0x3f3f3f3f, M = 1e7 + 10;
13

14
// 线段树节点结构体，用于维护区间最大值及其位置
15
class Node{
16
public:
17
    int l, r;    // 节点表示的区间范围 [l, r]
18
    int id;      // 当前区间内最大值所在的位置
19
    int ma;      // 当前区间内的最大值
20
};
21

22
Node tr[N * 4];  // 线段树数组，四倍空间防止越界
23
int n, m;        // n: 物品数量, m: 箱子容量
24
int a[N], b[N];  // a[i]: 第i个物品的体积, b[i]: 第i个箱子的剩余空间
25

26
// 合并两个子节点的信息，更新父节点的最大值和位置
27
void pushup(Node& u, Node& l, Node& r){
28
    if(l.ma >= r.ma){
29
        u.id = l.id, u.ma = l.ma;  // 左子树最大值更大，更新为左子树的信息
30
    }
31
    else u.id = r.id,u.ma = r.ma; // 右子树最大值更大，更新为右子树的信息
32
}
33

34
// 重载函数：通过节点编号调用pushup，合并左右子树信息
35
void pushup(int u){
36
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
37
}
38

39
// 构建线段树，初始化每个叶子节点的值
40
void build(int u,int l, int r){
41
    tr[u].l = l, tr[u].r = r;
42
    if(l == r){
43
        tr[u].ma = 0;    // 初始时所有箱子的剩余空间都是0
44
        tr[u].id = l;    // 记录位置
45
    }
46
    else{
47
        int mid = l + r >> 1;
48
        build(u << 1, l ,mid), build(u << 1 | 1, mid + 1, r);
49
        pushup(u);
50
    }
51
}
52

53
// 修改线段树中位置x的值为v，并更新相关节点的信息
54
void modify(int u,int x, int v){
55
    if(tr[u].l == x && tr[u].r == x){
56
        tr[u].ma = v;  // 找到目标位置，更新值
57
    }
58
    else{
59
        int mid = tr[u].l + tr[u].r >> 1;
60
        if(x <= mid) modify(u << 1, x, v);  // 目标在左子树
61
        else modify(u << 1 | 1, x, v);      // 目标在右子树
62
        pushup(u);  // 更新当前节点的信息
63
    }
64
}
65

66
// 查询第一个剩余空间大于等于x的箱子位置
67
// 如果没有这样的箱子，返回0
68
int query(int u, int x){
69
    if(tr[u].ma < x) return 0;  // 当前区间最大值都小于x，无解
70
    if(tr[u].l == tr[u].r){
71
        return tr[u].id;  // 找到叶子节点，返回位置
72
    }
73
    if(tr[u << 1].ma >= x){  // 左子树有解，优先在左子树查找
74
        return query(u << 1, x);
75
    }
76
    return query(u << 1 | 1, x);  // 否则在右子树查找
77
}
78

79
// 首次适应算法（First Fit）
80
// 策略：将物品放入第一个能容纳它的箱子
81
int firstfit(){
82
    build(1, 1, n);  // 构建线段树，维护箱子剩余空间
83
    int cnt = 0;     // 当前使用的箱子数量
84

85
    for(int i = 1; i <= n; i++){
86
        int t = query(1, a[i]);  // 查询第一个能容纳当前物品的箱子
87

88
        if(t){
89
            // 找到合适的箱子，将物品放入
90
            b[t] -= a[i];              // 更新箱子剩余空间
91
            modify(1, t, b[t]);        // 在线段树中更新这个箱子的剩余空间
92
        }
93
        else{
94
            // 没有找到合适的箱子，创建新箱子
95
            b[++cnt] = m - a[i];         // 新箱子的剩余空间 = 容量 - 物品体积
96
            modify(1, cnt, b[cnt]);      // 在线段树中添加新箱子
97
        }
98
    }
99
    return cnt;  // 返回使用的箱子总数
100
}
101

102
// 最佳适应算法（Best Fit）
103
// 策略：将物品放入能容纳它且剩余空间最小的箱子
104
int Bestfit(){
105
    multiset<int> A;  // 用multiset维护所有箱子的剩余空间，自动排序
106
    int cnt = 0;      // 当前使用的箱子数量
107

108
    for(int i = 1; i <= n; i++){
109
        // 找到第一个剩余空间 >= 当前物品体积的箱子
110
        auto it = A.lower_bound(a[i]);
111

112
        if(it != A.end()){
113
            // 找到合适的箱子，将物品放入
114
            int t = *it - a[i];    // 计算放入后的剩余空间
115
            A.erase(it);           // 从multiset中删除原剩余空间
116
            A.insert(t);           // 插入新的剩余空间
117
        }else{
118
            // 没有找到合适的箱子，创建新箱子
119
            A.insert(m - a[i]);    // 插入新箱子的剩余空间
120
            cnt++;                 // 箱子数量增加
121
        }
122
    }
123
    return cnt;  // 返回使用的箱子总数
124
}
125

126
// 处理单个测试用例
127
void solve() {
128
    cin >> n >> m;  // 读入物品数量和箱子容量
129

130
    for (int i = 1; i <= n; i++) cin >> a[i];  // 读入每个物品的体积
131

132
    // 输出两种算法的结果：首次适应算法和最佳适应算法
133
    cout << firstfit() << " " << Bestfit()<< endl;
134
}
135

136
// 主函数
137
signed main() {
138
    IOS;  // 加速IO操作
139

140
    int _;  // 测试用例数量
141
    cin >> _;
142

143
    // 处理每个测试用例
144
    while (_--) {
145
        solve();
146
    }
147

148
    return 0;
149
}

Bin Packing Problem

https://blog.rookiesama.space/posts/题解/bin-packing-problem/

作者

Rookiesama

发布于