如何设计最优算法实现 crate 推送距离最大化？

问题背景 #

CratePushers公司雇佣员工推送箱子，员工属性如下：

• 每位员工有特定推送效率（如Alice为3英尺/美元，Bob为2英尺/美元）
• 每位员工仅能推送特定类型的箱子（如Alice可推A、B、C型，Bob可推A、D型）
• 每位员工有推送箱子的数量上限（如Alice单次任务最多推2个箱子）
• 每位员工有薪酬上限（如Alice单次任务最多接受35美元，忽略该属性的方案也可）

现有若干箱子，每个箱子有独立预算（如5个箱子A-E，每个预算20美元，仅可用于对应箱子），目标是最大化所有箱子的总推送距离，需优化资金分配：雇佣哪位员工推哪个箱子，支付多少金额？

输入示例 #

员工属性列表 #

[
  {
    name: 'Alice',
    capableOfPushing: ['A', 'B', 'C'],
    paymentLimit: 35,
    crateLimit: 2,
    efficiency: 3, // Feet per dollar
  },
  {
    name: 'Bob',
    capableOfPushing: ['A', 'D'],
    paymentLimit: null,
    crateLimit: null,
    efficiency: 2,
  }
]

箱子预算列表 #

[
  {
    crate: 'A',
    budget: 20,
  },
  {
    crate: 'B',
    budget: 20
  },
  {
    crate: 'C',
    budget: 20
  },
  {
    crate: 'D',
    budget: 20
  },
  {
    crate: 'E',
    budget: 20
  },
]

输出示例 #

最优分配方案之一：

[
  {
    employee: 'Alice',
    crate: 'B',
    amountPaid: 20,
  },
  {
    employee: 'Alice',
    crate: 'C',
    amountPaid: 15,
  },
  {
    employee: 'Bob',
    crate: 'A',
    amountPaid: 20,
  },
  {
    employee: 'Bob',
    crate: 'D',
    amountPaid: 20,
  }
]

（无人可推E型箱，对应预算留存）

若B型箱预算低于5美元，最优方案为：支付Alice 15美元推A型箱、20美元推C型箱；支付Bob 5美元推A型箱、20美元推D型箱，放弃B型箱推送以最大化总距离。

已尝试但无效的方案 #

• 暴力枚举：生成所有箱子推送组合，当员工属性数值较大时（如Alice可推30种箱、上限10个），复杂度极高（数千万级场景），无法扩展。
• 动态规划：受箱子数量上限约束，难以确定各阶段最优解。
• 查找LeetCode类似问题：未找到匹配场景。
• 多商品最大流（multi-commodity max flow）：难以将员工属性转化为图结构，箱子数量上限仍是瓶颈，虽为较有潜力的方向但未突破。

内容的提问来源于stack exchange，提问作者Zevgon