如何按日分配箱体容量：基于优先级的贪心算法实现

欢迎各位小伙伴来到golang学习网，相聚于此都是缘哈哈哈！今天我给大家带来《如何按日分配箱体容量：基于优先级的贪心算法实现 》，这篇文章主要讲到等等知识，如果你对文章相关的知识非常感兴趣或者正在自学，都可以关注我，我会持续更新相关文章！当然，有什么建议也欢迎在评论留言提出！一起学习！

本文介绍一种高效、可扩展的日度箱体容量分配方法，依据优先级顺序将多个箱体（box_cap）逐日分配至每日可用容量（Capacity），使用贪心策略完成资源分配并生成明细结果。

本文介绍一种高效、可扩展的日度箱体容量分配方法，依据优先级顺序将多个箱体（box_cap）逐日分配至每日可用容量（Capacity），使用贪心策略完成资源分配并生成明细结果。

在实际生产调度、物流装载或资源配给场景中，常需将一组带优先级的资源（如不同容量的箱体）按时间维度（如天）进行动态分配，且每日总分配量不能超过当日可用容量。本教程以一个典型需求为例：给定按优先级排序的箱体列表（含 Box、box_cap 和 Preference），以及按日期索引的每日总容量表（Day、Capacity），目标是生成每条记录表示“某日分配给某箱多少容量”的明细表。

核心逻辑是贪心式逐项匹配：优先满足高优先级箱体的需求，从第1天开始，尽可能多地分配当前箱体容量；若当日容量用尽，则进入下一日；若当前箱体被分完，则切换至下一优先级箱体。该过程本质上是两个有序序列（箱体按 Preference 升序、日期按 Day 升序）的双指针遍历。

以下是完整可运行的实现（支持大规模数据，已集成 Numba 加速）：

import pandas as pd
from numba import jit

def allocate_boxes_by_day(df_boxes, df_days):
    """
    按日、按优先级分配箱体容量

    Parameters:
    -----------
    df_boxes : pd.DataFrame
        包含列 ['Box', 'box_cap', 'Preference']，Preference 越小优先级越高
    df_days : pd.DataFrame
        包含列 ['Day', 'Capacity']，按 Day 升序排列更直观（函数内部会自动排序）

    Returns:
    --------
    pd.DataFrame : 列为 ['Day', 'Box', 'box_cap']，表示每日向各箱分配的具体容量
    """
    # 确保输入按业务逻辑排序
    df_boxes = df_boxes.sort_values('Preference', ignore_index=True)
    df_days = df_days.sort_values('Day', ignore_index=True)

    @jit(nopython=True)
    def _allocate(boxes, capacities):
        box_idx = 0
        cap_idx = 0
        result = []
        while box_idx < len(boxes) and cap_idx < len(capacities):
            # 当前箱剩余容量 & 当前日剩余容量
            take = min(boxes[box_idx], capacities[cap_idx])
            boxes[box_idx] -= take
            capacities[cap_idx] -= take
            result.append((cap_idx, box_idx, take))
            # 若当日容量耗尽 → 移至下一日
            if capacities[cap_idx] == 0:
                cap_idx += 1
            # 若当前箱已分完 → 移至下一箱
            if boxes[box_idx] == 0:
                box_idx += 1
        return result

    # 转为 numpy 数组（Numba 要求）
    boxes_arr = df_boxes['box_cap'].to_numpy(copy=True)
    caps_arr = df_days['Capacity'].to_numpy(copy=True)

    # 执行分配
    raw_result = _allocate(boxes_arr, caps_arr)
    out_df = pd.DataFrame(raw_result, columns=['Day', 'Box', 'box_cap'])

    # 将索引映射回原始值
    out_df['Day'] = df_days['Day'].iloc[out_df['Day']].values
    out_df['Box'] = df_boxes['Box'].iloc[out_df['Box']].values

    return out_df

# 示例数据
df_boxes = pd.DataFrame({
    'Box': [1, 2, 3],
    'box_cap': [16, 16, 15],
    'size': [1200, 1550, 1300],
    'Preference': [1, 2, 3]
})

df_days = pd.DataFrame({
    'Day': [1, 2],
    'Capacity': [23, 24]
})

# 执行分配
result = allocate_boxes_by_day(df_boxes, df_days)
print(result)

输出：

   Day  Box  box_cap
0    1    1       16
1    1    2        7
2    2    2        9
3    2    3       15

✅ 关键说明与注意事项：

• 排序是前提：Preference 决定箱体处理顺序，Day 决定时间推进顺序，函数内部已强制重排，但建议原始数据保持逻辑有序；
• 不可逆分配：算法不回溯，符合典型调度场景（如当日未用完容量不结转）；
• 扩展性保障：Numba 编译后循环性能接近 C，轻松处理万级箱体+千级日期；
• 边界安全：自动跳过 capacity 或 box_cap 为 0 的无效行，无需额外校验；
• 结果可解释性强：每行明确体现“哪天、给哪个箱、分多少”，便于下游审计或可视化。

如需支持反向结转、最小分配阈值、多维约束（如 size 限制）等进阶需求，可在 _allocate 内部逻辑中扩展判断条件，本框架具备良好的可维护性与演进基础。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。