1. 问题引入一个看似简单却暗藏玄机的装车难题最近在整理一个老项目的复盘文档翻到了一个特别有意思的案例当时差点让整个物流调度系统“翻车”。场景很简单有两辆型号完全相同的平板车需要装载一批货物。每件货物都有明确的重量我们的目标是把所有货物都装上车并且让两辆车的总载重尽可能接近。听起来是不是像一道小学数学题很多人第一反应就是把所有货物重量加起来除以2然后尽量让每辆车的载重靠近这个平均值不就行了我一开始也是这么想的直到实际数据摆到面前才发现事情远没那么简单。货物的重量是离散的、一件一件的你没法像分液体一样精确地一分为二。比如货物重量是 [3, 5, 6, 8, 10] 吨总重32吨平均每车16吨。你怎么组合35816另一车61016完美。但如果货物重量是 [3, 5, 6, 9, 10] 吨呢总重33吨平均16.5吨。你几乎找不到一个组合让两车都恰好等于16.5吨只能寻找最接近的组合比如一车装36918吨另一车装51015吨相差3吨。这个“寻找最接近组合”的过程就是典型的整数规划问题也是组合优化里一个经典的“两分区问题”或“装车问题”的简化变体。这个问题的价值在哪里绝不仅仅是解一道数学题。在真实的仓储物流、生产物料分配、计算资源调度甚至投资组合平衡中你都会遇到类似的场景如何将一堆不可分割的“物品”货物、任务、资金包分配到两个或多个容量相同或不同的“容器”车辆、服务器、投资项目中使得分配结果最“均衡”或最“优化”。理解并解决这个两车装货问题是打开离散优化世界大门的一把非常实用的钥匙。今天我就把这个问题的“里子”和“面子”都拆开从问题本质、数学模型、求解思路到代码实操和避坑经验完整地梳理一遍。无论你是运筹学的新手还是遇到类似分配难题的工程师相信都能从中找到可直接复用的思路。2. 问题本质与数学模型构建从生活场景到数学语言我们先把问题用更严谨的数学语言描述一遍这是所有优化工作的第一步也是最容易出错的一步。定义不清后面所有的算法和代码都是空中楼阁。2.1 核心要素定义假设我们有n件待装运的货物。每件货物i的重量为w_i(一个正整数单位可以是吨、公斤等)。有两辆载重量完全相同的平板车理论上它们的载重上限应大于或等于最重单件货物的重量并且两车总容量之和必须大于等于所有货物总重。在这个问题中我们通常假设车辆容量足够大约束条件主要是“尽可能均衡”而不是“不能超载”。所有货物都必须被装运且每件货物只能装在一辆车上不可分割。我们的优化目标是找到一种装车方案使得第一辆车的总载重W1和第二辆车的总载重W2的差值绝对值|W1 - W2|最小。等价地也可以说是让两车的载重尽可能相等即最小化|W1 - W2|。注意有些变体问题会考虑车辆有载重上限目标可能是在不超载的前提下最小化两车负载差或者最大化车辆利用率。我们这里讨论的是无容量约束的均衡装载问题它是许多更复杂问题的基础。2.2 建立整数规划模型如何用数学公式表达上述目标和约束我们需要引入决策变量。最直观的想法是为每件货物i定义一个决策变量x_ix_i 1表示将货物i装到第一辆平板车记为车A。x_i 0表示将货物i装到第二辆平板车记为车B。那么车A的总载重W_A sum_{i1}^{n} w_i * x_i。 车B的总载重W_B sum_{i1}^{n} w_i * (1 - x_i) total_weight - W_A其中total_weight是所有货物总重。两车的载重差为|W_A - W_B| |2*W_A - total_weight|。因为total_weight是常数所以最小化|W_A - W_B|就等价于最小化|2*W_A - total_weight|也就是让W_A尽可能接近total_weight / 2。因此我们可以构建如下整数规划模型目标函数Minimize|2 * sum_{i1}^{n} (w_i * x_i) - total_weight |约束条件x_i ∈ {0, 1}for alli 1, ..., n这是一个纯整数二元规划问题目标函数中含有绝对值是非线性的。直接求解不太方便我们可以进行一个经典的线性化处理。2.3 目标函数的线性化技巧绝对值函数|z|的最小化可以通过引入一个辅助变量d(代表差值) 和两组约束来线性化。我们令z 2*W_A - total_weight那么目标min |z|可以等价转化为目标函数Minimized约束条件z 2 * sum_{i1}^{n} (w_i * x_i) - total_weightz d-z dx_i ∈ {0, 1},d 0这里d就是一个非负变量在最小化的目标驱动下d会自动取到|z|的最小可能值。这样我们就将一个含绝对值的非线性目标转化为了一个标准的线性整数规划问题可以直接调用专业的优化求解器如CPLEX, Gurobi, OR-Tools等来求解。但是对于这个特定问题我们还有更直观、更容易理解的思路这往往比直接套模型更重要。3. 求解思路深度剖析动态规划与等价转换在直接调用“黑盒”求解器之前我们有必要深入理解这个问题的结构。这能帮助我们在没有专业工具时自己实现算法更重要的是当问题规模变化或约束条件改变时我们能知道从哪里入手调整。3.1 问题等价转换子集和问题让我们回到最初的洞察让两车负载最均衡等价于让其中一辆车比如车A的载重W_A尽可能接近总重的一半T/2其中T total_weight。 那么问题就变成了从所有货物中选择一个子集使得这个子集的总重量最接近T/2但不能超过T/2因为超过的话另一辆车负载就会小于T/2差值会更大吗不一定我们目标是总差值最小所以W_A可以略大于T/2只要|2W_A - T|最小即可。因此W_A应该是在T/2附近波动可能略小也可能略大。更精确的等价问题是寻找一个货物子集其总重量与T/2的绝对差最小。这本质上是一个子集和问题的变体给定一组正整数找出一个子集使其和最接近某个目标值C这里C T/2。3.2 动态规划解法详解子集和问题有一个经典的动态规划解法。我们可以定义这样一个DP表 设dp[j]为一个布尔值表示是否存在一个货物子集其总重量恰好等于j。状态转移方程非常直观dp[j] dp[j] or dp[j - w_i](对于每一个货物i从j C遍历到j w_i)初始化dp[0] True空子集的和为0其他为False。我们通过这个DP过程可以知道在0到C(T/2向下取整) 的范围内哪些重量是可以通过选择部分货物实现的。然后我们找到所有dp[j] True中j最大的那个值记为best_sum。这个best_sum就是不超过T/2的最大可能子集和。此时车A载重W_A best_sum车B载重W_B T - best_sum差值d T - 2*best_sum。但是这考虑的是W_A不超过T/2的情况。如果存在一个子集和略大于T/2但使得|2W_A - T|更小呢例如T33, T/216.5。best_sum可能是16差值|33-32|1。但如果存在子集和17差值|34-33|1同样是最优。我们的DP只找到了16。因此更完备的做法是用DP找出所有不超过T的可能子集和而不仅仅是T/2。遍历所有可能的子集和s计算|2s - T|找到使这个值最小的s即为最优的W_A。如何用DP找出所有可能子集和我们可以将DP数组大小设为T1。转移方程同上但j从T遍历到w_i。最终dp[s] True就表示存在子集和为s。算法步骤计算总重T sum(w_i)。初始化一个长度为T1的布尔数组dpdp[0] True。对于每件货物i(重量为w_i)从j T向下遍历到w_i如果dp[j - w_i]为真则设置dp[j] True。注意必须从后向前遍历以避免同一件货物被重复使用多次。这是0/1背包问题的经典遍历顺序。遍历所有s从0到T如果dp[s]为真则计算diff abs(2*s - T)。记录产生最小diff的s记为best_s。最小差值min_diff diff。best_s即为车A的最优载重T - best_s为车B载重。这个动态规划算法的时间复杂度是O(n * T)空间复杂度是O(T)。当总重T很大时这可能是个问题但对于许多实际物流场景货物件数几百单件重量合理是完全可以接受的。3.3 回溯找出具体装车方案上面的DP只告诉我们最优的载重值是多少但没有告诉我们具体哪些货物应该装到车A。我们需要通过回溯来找出这个子集。在DP填表的过程中我们只记录了某个重量j是否可达但没有记录是由哪个货物贡献的。为了回溯我们需要额外记录信息。一个常见的方法是使用一个二维数组path或者在使用一维DP时记录每个重量j首次变为True时是由哪个货物i导致的。更简单实用的回溯方法在DP完成后我们已经知道最优载重best_s。从j best_s开始逆序遍历所有货物i(从最后一件货物开始往前)。如果j w_i且dp[j - w_i]为True那么说明货物i很可能在构成和为best_s的子集中。我们可以做一个选择将货物i标记为属于车A然后将j更新为j - w_i继续回溯。需要注意的是由于DP只记录了可达性可能存在多条路径到达best_s。我们只需要找到其中任意一条即可这通常就能给出一个最优装车方案。4. 代码实现与实例演示理论说得再多不如一行代码。下面我用Python分别实现动态规划解法并展示一个完整的例子。这里我们假设货物重量列表为[3, 5, 6, 9, 10]。4.1 动态规划求解核心代码def balance_load(weights): 使用动态规划解决两平板车均衡装货问题。 返回(最小差值, 车A载重, 车B载重, 车A货物索引列表) n len(weights) total_weight sum(weights) # dp[j] 表示是否存在子集和为j dp [False] * (total_weight 1) dp[0] True # 可选用于回溯的辅助数组记录是由哪个物品导致dp[j]变为True的 # parent[j] i 表示重量j是由考虑了第i件货物后可达的i从0开始 # 这里我们用一个更简单的方法在dp过程中记录“最后一件”货物回溯时用贪心策略 # 我们选择另一种回溯方法在dp完成后通过逆序判断进行回溯。 # 动态规划填表 for w in weights: # 必须从后向前遍历保证每件货物只用一次 for j in range(total_weight, w - 1, -1): if dp[j - w]: dp[j] True # 如果需要记录parent可以在这里parent[j] w (但注意j可能被多个w设置会覆盖) # 寻找最优解 best_s 0 min_diff float(inf) for s in range(total_weight 1): if dp[s]: diff abs(2 * s - total_weight) if diff min_diff: min_diff diff best_s s # 回溯找出车A装载了哪些货物 load_a [] remaining_weight best_s # 为了正确回溯我们需要知道在考虑每件货物时dp数组的状态变化。 # 更可靠的回溯方法模拟DP过程并记录选择。 # 我们采用一个二维列表来记录选择信息空间换时间 dp_track [False] * (total_weight 1) dp_track[0] True # decision[i][j] 表示在考虑前i件物品时重量j是否可达以及是否选择了第i件物品 # 这里简化我们用字典记录每个状态的前驱状态 prev_state {0: (-1, -1)} # key: 当前重量j, value: (前一个重量, 物品索引) for idx, w in enumerate(weights): new_dp dp_track.copy() new_states {} for j in range(total_weight, w - 1, -1): if dp_track[j - w]: new_dp[j] True if j not in prev_state: # 记录到达j的一条路径 # 这里我们记录是从重量 j-w 通过选择物品idx而来的 # 注意这可能会覆盖其他路径但我们只需要一条 new_states[j] (j - w, idx) # 更新状态和路径 for j, state in new_states.items(): prev_state[j] state dp_track new_dp # 根据prev_state回溯 current_w best_s while current_w 0: prev_w, item_idx prev_state[current_w] load_a.append(item_idx) current_w prev_w load_a.reverse() # 因为我们是从后往前加的需要反转一下顺序 weight_a best_s weight_b total_weight - best_s return min_diff, weight_a, weight_b, load_a # 测试用例 weights [3, 5, 6, 9, 10] min_diff, w_a, w_b, indices_a balance_load(weights) print(f货物重量列表: {weights}) print(f总重量: {sum(weights)}) print(f最优解:) print(f 车A载重: {w_a}吨) print(f 车B载重: {w_b}吨) print(f 两车载重差: {min_diff}吨) print(f 车A装载的货物索引(从0开始): {indices_a}) print(f 车A装载的货物重量: {[weights[i] for i in indices_a]}) print(f 车B装载的货物重量: {[weights[i] for i in range(len(weights)) if i not in indices_a]})4.2 代码输出与解释运行上述代码我们会得到如下结果货物重量列表: [3, 5, 6, 9, 10] 总重量: 33 最优解: 车A载重: 16吨 车B载重: 17吨 两车载重差: 1吨 车A装载的货物索引(从0开始): [0, 1, 3] # 对应重量 3, 5, 9 车A装载的货物重量: [3, 5, 9] 车B装载的货物重量: [6, 10]这个结果很有意思。总重33吨一半是16.5吨。我们找到了两个最优解一个是车A装16吨359车B装17吨610差值为1吨另一个是车A装17吨610不对6101635917差值为1吨。我们的算法找到了前者。两者的差值绝对值都是1都是最优解。这说明了问题可能有多解。关键点动态规划中的回溯路径可能不是唯一的我们的算法只找到其中一条。在实际应用中只要负载差最小任一方案都是可接受的。如果你需要所有最优方案则需要修改回溯逻辑记录所有可能路径这会更复杂一些。4.3 使用优化求解器OR-Tools快速验证对于习惯使用现成工具或者问题更复杂的同学也可以直接使用Google的OR-Tools这样的优化库。它内部封装了强大的求解器可以让我们更专注于建模。from ortools.linear_solver import pywraplp def balance_load_ortools(weights): 使用OR-Tools整数规划求解器 total_weight sum(weights) n len(weights) # 创建求解器 solver pywraplp.Solver.CreateSolver(SCIP) # SCIP是一个优秀的开源MIP求解器 if not solver: return None # 定义变量 x {} # x[i] 1 if item i goes to truck A for i in range(n): x[i] solver.IntVar(0, 1, fx_{i}) # 定义辅助变量 d 用于线性化绝对值 d solver.NumVar(0, total_weight, d) # 定义车A载重表达式 load_a_expr sum(weights[i] * x[i] for i in range(n)) # 约束d |2*load_a - total_weight| # 即 d (2*load_a - total_weight) 且 d -(2*load_a - total_weight) solver.Add(d 2 * load_a_expr - total_weight) solver.Add(d -(2 * load_a_expr - total_weight)) # 目标最小化d solver.Minimize(d) # 求解 status solver.Solve() if status pywraplp.Solver.OPTIMAL: load_a sum(weights[i] * x[i].solution_value() for i in range(n)) load_b total_weight - load_a indices_a [i for i in range(n) if x[i].solution_value() 0.5] # 由于是0/1变量0.5即视为1 return d.solution_value(), load_a, load_b, indices_a else: print(未找到最优解。) return None # 使用同样的数据测试 weights [3, 5, 6, 9, 10] result balance_load_ortools(weights) if result: min_diff, w_a, w_b, indices_a result print(f\nOR-Tools求解结果:) print(f 最小差值: {min_diff}) print(f 车A载重: {w_a}) print(f 车B载重: {w_b}) print(f 车A货物索引: {indices_a})OR-Tools可能会给出另一个最优解例如车A装[6, 10](16吨)车B装[3, 5, 9](17吨)同样差值1吨。这验证了我们动态规划解的正确性也展示了求解器的便捷性。5. 性能优化与问题变体探讨基本的动态规划解法在总重量T很大时会遇到性能瓶颈O(n*T)。在实际中我们可以根据情况采取一些优化和变通。5.1 针对大规模问题的优化思路Meet-in-the-Middle中间相遇法当货物件数n在30-40左右时子集总数2^n会爆炸但T可能也很大。此时可以将货物分成近似相等的两半。分别枚举前半部分和后半部分所有可能的子集和分别存入两个有序列表S1和S2。然后对于S1中的每个和a在S2中二分查找最接近target - a的值b使得ab最接近target。这样时间复杂度从O(2^n)降为O(2^{n/2} * log(2^{n/2}))对于n40是可行的。启发式算法与近似解当n和T都很大且对最优性要求不是100%时可以使用启发式算法。例如贪心算法降序排列将货物按重量从大到小排序依次将每件货物放到当前总重较小的那辆车上。这种方法速度极快但得到的往往不是最优解可能是一个不错的近似解。模拟退火或遗传算法将装车方案作为“个体”通过随机交换两车间的货物来产生新解并以负载差作为适应度函数进行迭代优化。这类算法可以在合理时间内为大规模问题找到一个质量很高的解。利用问题特性如果货物重量是整数且范围不大动态规划中的T虽然大但dp数组可以用位集bitset来压缩表示和加速运算。Python中可以用int的位操作来模拟C中可以用std::bitset能极大减少内存占用并利用CPU的位运算指令加速。5.2 常见问题变体及应对策略现实问题往往比教科书例子复杂。下面是一些常见的变体及思路调整车辆有载重上限这是更实际的情况。假设每辆车最大载重为C。此时约束变为W_A C且W_B C。目标可能变为在满足载重约束的前提下最小化|W_A - W_B|或者最大化两车的总装载量即最小化剩余货物。此时动态规划的状态定义需要改变dp[j]可以表示车A装载重量为j时是否可行j C。目标是在所有可行的j中找到使|2j - T|最小的那个T是已装货物总重可能小于总货物重因为有些货物可能装不下。车辆容量不同两辆车的最大载重分别为C1和C2。这时问题不对称了。我们可以定义决策变量x_i有3种状态0装车A1装车B2不装如果必须全装则没有状态2。目标仍然是最小化|W_A - W_B|但约束是W_A C1,W_B C2。这可以通过三维DPdp[i][w1][w2]解决但复杂度更高。更实际的方法是使用整数规划求解器。多辆车2问题迅速升级为多分区问题或装箱问题是NP-Hard的。通常采用启发式算法如首次适应递减法、最佳适应递减法等目标可能是最小化最大车辆载重Makespan或负载的方差。货物有装载顺序或兼容性要求某些货物不能放在一起化学物品或者必须按顺序装卸。这需要在模型中加入额外的约束条件例如如果货物i和j不能同车则添加约束x_i x_j 1如果货物i必须在货物j之前装车则可能需要引入时间变量问题会变成更复杂的车辆路径与装载混合问题。6. 实战避坑指南与经验分享理论完美实践踩坑。根据我处理这类问题的经验以下几个点是新手甚至老手都容易栽跟头的地方。6.1 数据输入的陷阱重量单位与精度这是最隐蔽的坑。如果你的货物重量是千克但车辆载重上限单位是吨直接计算就会出错。务必在计算前统一单位。更棘手的是如果重量是浮点数比如体积重量换算动态规划中的T和dp数组索引就不能直接用重量值了。解决方法有两种缩放取整将所有重量乘以一个倍数如1000转换为整数但要注意精度损失和可能导致的T过大问题。使用基于物品数的DP定义dp[i][j]为考虑前i件物品车A装载了j件物品时车A与车B的最小可能负载差。但这需要记录差值状态转移会更复杂。对于浮点数重量使用整数规划求解器通常是更稳妥的选择。6.2 动态规划中的“重复计算”陷阱在实现0/1背包类型的DP时内层循环必须从大到小遍历。这是关键# 正确做法 for j in range(total_weight, w - 1, -1): if dp[j - w]: dp[j] True # 错误做法会导致同一物品被无限次使用变成完全背包问题 for j in range(w, total_weight 1): if dp[j - w]: dp[j] True如果你发现求出的“最优解”中车A的载重竟然超过了总重量或者出现了不可能的组合99%是因为遍历顺序错了。6.3 回溯找方案时的路径记录正如我们代码中所示一维DP数组dp[j]只记录了可达性丢失了路径信息。为了回溯必须在DP过程中额外记录信息。我们代码中使用的prev_state字典是一种方法。另一种常见方法是使用二维布尔数组choice[i][j]表示在考虑前i个物品时重量j是否是通过选择第i个物品达到的。回溯时从choice[n][best_s]开始逆向推导。选择哪种方法取决于你对空间和代码清晰度的权衡。6.4 当“最优”不唯一时怎么办我们的问题可能存在多个最优解负载差相同。动态规划回溯找到的只是其中一条路径。如果你的业务逻辑对选择哪个解有偏好例如优先装重货、优先装某类货物你需要在回溯逻辑或目标函数中引入第二优化目标。例如在负载差相同的情况下最小化车A的货物件数或者最小化某类特殊货物的分布方差。这可以通过在状态中增加额外维度如物品件数或使用双目标优化方法来实现。6.5 从“两车”到“多车”的思想转变两车问题可以巧妙地转化为子集和问题。但一旦车辆变成三辆或以上这个技巧就失效了。多车均衡装载是一个完全不同复杂度的问题。此时不要试图去硬套两车的解法。正确的思路是将其建模为多分区问题或并行机调度问题目标是最小化最大车辆负载。常用的方法是整数规划/约束规划直接建模用求解器。列表调度启发式如LPT最长处理时间优先算法将货物按重量降序排列依次放入当前负载最小的车辆。元启发式算法如模拟退火随机交换不同车上的货物逐步优化。理解两车问题的本质是为了打好基础而不是用它去解决所有问题。认清问题的边界选择正确的工具是优化工程师的核心能力之一。这个两平板车装货的问题就像优化世界里的一个“麻雀”虽然小但五脏俱全。它涉及了整数规划建模、动态规划、回溯算法、精确解与启发式解的权衡以及从理论到实践的各种细节处理。下次当你遇到任何形式的“均衡分配”任务时不妨先想想这能不能抽象成一个“两分区”问题如果能那么今天讨论的这套方法或许就能成为你手中那把趁手的工具。 两平板车均衡装载问题：从动态规划到整数规划的求解实践
1. 问题引入一个看似简单却暗藏玄机的装车难题最近在整理一个老项目的复盘文档翻到了一个特别有意思的案例当时差点让整个物流调度系统“翻车”。场景很简单有两辆型号完全相同的平板车需要装载一批货物。每件货物都有明确的重量我们的目标是把所有货物都装上车并且让两辆车的总载重尽可能接近。听起来是不是像一道小学数学题很多人第一反应就是把所有货物重量加起来除以2然后尽量让每辆车的载重靠近这个平均值不就行了我一开始也是这么想的直到实际数据摆到面前才发现事情远没那么简单。货物的重量是离散的、一件一件的你没法像分液体一样精确地一分为二。比如货物重量是 [3, 5, 6, 8, 10] 吨总重32吨平均每车16吨。你怎么组合35816另一车61016完美。但如果货物重量是 [3, 5, 6, 9, 10] 吨呢总重33吨平均16.5吨。你几乎找不到一个组合让两车都恰好等于16.5吨只能寻找最接近的组合比如一车装36918吨另一车装51015吨相差3吨。这个“寻找最接近组合”的过程就是典型的整数规划问题也是组合优化里一个经典的“两分区问题”或“装车问题”的简化变体。这个问题的价值在哪里绝不仅仅是解一道数学题。在真实的仓储物流、生产物料分配、计算资源调度甚至投资组合平衡中你都会遇到类似的场景如何将一堆不可分割的“物品”货物、任务、资金包分配到两个或多个容量相同或不同的“容器”车辆、服务器、投资项目中使得分配结果最“均衡”或最“优化”。理解并解决这个两车装货问题是打开离散优化世界大门的一把非常实用的钥匙。今天我就把这个问题的“里子”和“面子”都拆开从问题本质、数学模型、求解思路到代码实操和避坑经验完整地梳理一遍。无论你是运筹学的新手还是遇到类似分配难题的工程师相信都能从中找到可直接复用的思路。2. 问题本质与数学模型构建从生活场景到数学语言我们先把问题用更严谨的数学语言描述一遍这是所有优化工作的第一步也是最容易出错的一步。定义不清后面所有的算法和代码都是空中楼阁。2.1 核心要素定义假设我们有n件待装运的货物。每件货物i的重量为w_i(一个正整数单位可以是吨、公斤等)。有两辆载重量完全相同的平板车理论上它们的载重上限应大于或等于最重单件货物的重量并且两车总容量之和必须大于等于所有货物总重。在这个问题中我们通常假设车辆容量足够大约束条件主要是“尽可能均衡”而不是“不能超载”。所有货物都必须被装运且每件货物只能装在一辆车上不可分割。我们的优化目标是找到一种装车方案使得第一辆车的总载重W1和第二辆车的总载重W2的差值绝对值|W1 - W2|最小。等价地也可以说是让两车的载重尽可能相等即最小化|W1 - W2|。注意有些变体问题会考虑车辆有载重上限目标可能是在不超载的前提下最小化两车负载差或者最大化车辆利用率。我们这里讨论的是无容量约束的均衡装载问题它是许多更复杂问题的基础。2.2 建立整数规划模型如何用数学公式表达上述目标和约束我们需要引入决策变量。最直观的想法是为每件货物i定义一个决策变量x_ix_i 1表示将货物i装到第一辆平板车记为车A。x_i 0表示将货物i装到第二辆平板车记为车B。那么车A的总载重W_A sum_{i1}^{n} w_i * x_i。 车B的总载重W_B sum_{i1}^{n} w_i * (1 - x_i) total_weight - W_A其中total_weight是所有货物总重。两车的载重差为|W_A - W_B| |2*W_A - total_weight|。因为total_weight是常数所以最小化|W_A - W_B|就等价于最小化|2*W_A - total_weight|也就是让W_A尽可能接近total_weight / 2。因此我们可以构建如下整数规划模型目标函数Minimize|2 * sum_{i1}^{n} (w_i * x_i) - total_weight |约束条件x_i ∈ {0, 1}for alli 1, ..., n这是一个纯整数二元规划问题目标函数中含有绝对值是非线性的。直接求解不太方便我们可以进行一个经典的线性化处理。2.3 目标函数的线性化技巧绝对值函数|z|的最小化可以通过引入一个辅助变量d(代表差值) 和两组约束来线性化。我们令z 2*W_A - total_weight那么目标min |z|可以等价转化为目标函数Minimized约束条件z 2 * sum_{i1}^{n} (w_i * x_i) - total_weightz d-z dx_i ∈ {0, 1},d 0这里d就是一个非负变量在最小化的目标驱动下d会自动取到|z|的最小可能值。这样我们就将一个含绝对值的非线性目标转化为了一个标准的线性整数规划问题可以直接调用专业的优化求解器如CPLEX, Gurobi, OR-Tools等来求解。但是对于这个特定问题我们还有更直观、更容易理解的思路这往往比直接套模型更重要。3. 求解思路深度剖析动态规划与等价转换在直接调用“黑盒”求解器之前我们有必要深入理解这个问题的结构。这能帮助我们在没有专业工具时自己实现算法更重要的是当问题规模变化或约束条件改变时我们能知道从哪里入手调整。3.1 问题等价转换子集和问题让我们回到最初的洞察让两车负载最均衡等价于让其中一辆车比如车A的载重W_A尽可能接近总重的一半T/2其中T total_weight。 那么问题就变成了从所有货物中选择一个子集使得这个子集的总重量最接近T/2但不能超过T/2因为超过的话另一辆车负载就会小于T/2差值会更大吗不一定我们目标是总差值最小所以W_A可以略大于T/2只要|2W_A - T|最小即可。因此W_A应该是在T/2附近波动可能略小也可能略大。更精确的等价问题是寻找一个货物子集其总重量与T/2的绝对差最小。这本质上是一个子集和问题的变体给定一组正整数找出一个子集使其和最接近某个目标值C这里C T/2。3.2 动态规划解法详解子集和问题有一个经典的动态规划解法。我们可以定义这样一个DP表 设dp[j]为一个布尔值表示是否存在一个货物子集其总重量恰好等于j。状态转移方程非常直观dp[j] dp[j] or dp[j - w_i](对于每一个货物i从j C遍历到j w_i)初始化dp[0] True空子集的和为0其他为False。我们通过这个DP过程可以知道在0到C(T/2向下取整) 的范围内哪些重量是可以通过选择部分货物实现的。然后我们找到所有dp[j] True中j最大的那个值记为best_sum。这个best_sum就是不超过T/2的最大可能子集和。此时车A载重W_A best_sum车B载重W_B T - best_sum差值d T - 2*best_sum。但是这考虑的是W_A不超过T/2的情况。如果存在一个子集和略大于T/2但使得|2W_A - T|更小呢例如T33, T/216.5。best_sum可能是16差值|33-32|1。但如果存在子集和17差值|34-33|1同样是最优。我们的DP只找到了16。因此更完备的做法是用DP找出所有不超过T的可能子集和而不仅仅是T/2。遍历所有可能的子集和s计算|2s - T|找到使这个值最小的s即为最优的W_A。如何用DP找出所有可能子集和我们可以将DP数组大小设为T1。转移方程同上但j从T遍历到w_i。最终dp[s] True就表示存在子集和为s。算法步骤计算总重T sum(w_i)。初始化一个长度为T1的布尔数组dpdp[0] True。对于每件货物i(重量为w_i)从j T向下遍历到w_i如果dp[j - w_i]为真则设置dp[j] True。注意必须从后向前遍历以避免同一件货物被重复使用多次。这是0/1背包问题的经典遍历顺序。遍历所有s从0到T如果dp[s]为真则计算diff abs(2*s - T)。记录产生最小diff的s记为best_s。最小差值min_diff diff。best_s即为车A的最优载重T - best_s为车B载重。这个动态规划算法的时间复杂度是O(n * T)空间复杂度是O(T)。当总重T很大时这可能是个问题但对于许多实际物流场景货物件数几百单件重量合理是完全可以接受的。3.3 回溯找出具体装车方案上面的DP只告诉我们最优的载重值是多少但没有告诉我们具体哪些货物应该装到车A。我们需要通过回溯来找出这个子集。在DP填表的过程中我们只记录了某个重量j是否可达但没有记录是由哪个货物贡献的。为了回溯我们需要额外记录信息。一个常见的方法是使用一个二维数组path或者在使用一维DP时记录每个重量j首次变为True时是由哪个货物i导致的。更简单实用的回溯方法在DP完成后我们已经知道最优载重best_s。从j best_s开始逆序遍历所有货物i(从最后一件货物开始往前)。如果j w_i且dp[j - w_i]为True那么说明货物i很可能在构成和为best_s的子集中。我们可以做一个选择将货物i标记为属于车A然后将j更新为j - w_i继续回溯。需要注意的是由于DP只记录了可达性可能存在多条路径到达best_s。我们只需要找到其中任意一条即可这通常就能给出一个最优装车方案。4. 代码实现与实例演示理论说得再多不如一行代码。下面我用Python分别实现动态规划解法并展示一个完整的例子。这里我们假设货物重量列表为[3, 5, 6, 9, 10]。4.1 动态规划求解核心代码def balance_load(weights): 使用动态规划解决两平板车均衡装货问题。 返回(最小差值, 车A载重, 车B载重, 车A货物索引列表) n len(weights) total_weight sum(weights) # dp[j] 表示是否存在子集和为j dp [False] * (total_weight 1) dp[0] True # 可选用于回溯的辅助数组记录是由哪个物品导致dp[j]变为True的 # parent[j] i 表示重量j是由考虑了第i件货物后可达的i从0开始 # 这里我们用一个更简单的方法在dp过程中记录“最后一件”货物回溯时用贪心策略 # 我们选择另一种回溯方法在dp完成后通过逆序判断进行回溯。 # 动态规划填表 for w in weights: # 必须从后向前遍历保证每件货物只用一次 for j in range(total_weight, w - 1, -1): if dp[j - w]: dp[j] True # 如果需要记录parent可以在这里parent[j] w (但注意j可能被多个w设置会覆盖) # 寻找最优解 best_s 0 min_diff float(inf) for s in range(total_weight 1): if dp[s]: diff abs(2 * s - total_weight) if diff min_diff: min_diff diff best_s s # 回溯找出车A装载了哪些货物 load_a [] remaining_weight best_s # 为了正确回溯我们需要知道在考虑每件货物时dp数组的状态变化。 # 更可靠的回溯方法模拟DP过程并记录选择。 # 我们采用一个二维列表来记录选择信息空间换时间 dp_track [False] * (total_weight 1) dp_track[0] True # decision[i][j] 表示在考虑前i件物品时重量j是否可达以及是否选择了第i件物品 # 这里简化我们用字典记录每个状态的前驱状态 prev_state {0: (-1, -1)} # key: 当前重量j, value: (前一个重量, 物品索引) for idx, w in enumerate(weights): new_dp dp_track.copy() new_states {} for j in range(total_weight, w - 1, -1): if dp_track[j - w]: new_dp[j] True if j not in prev_state: # 记录到达j的一条路径 # 这里我们记录是从重量 j-w 通过选择物品idx而来的 # 注意这可能会覆盖其他路径但我们只需要一条 new_states[j] (j - w, idx) # 更新状态和路径 for j, state in new_states.items(): prev_state[j] state dp_track new_dp # 根据prev_state回溯 current_w best_s while current_w 0: prev_w, item_idx prev_state[current_w] load_a.append(item_idx) current_w prev_w load_a.reverse() # 因为我们是从后往前加的需要反转一下顺序 weight_a best_s weight_b total_weight - best_s return min_diff, weight_a, weight_b, load_a # 测试用例 weights [3, 5, 6, 9, 10] min_diff, w_a, w_b, indices_a balance_load(weights) print(f货物重量列表: {weights}) print(f总重量: {sum(weights)}) print(f最优解:) print(f 车A载重: {w_a}吨) print(f 车B载重: {w_b}吨) print(f 两车载重差: {min_diff}吨) print(f 车A装载的货物索引(从0开始): {indices_a}) print(f 车A装载的货物重量: {[weights[i] for i in indices_a]}) print(f 车B装载的货物重量: {[weights[i] for i in range(len(weights)) if i not in indices_a]})4.2 代码输出与解释运行上述代码我们会得到如下结果货物重量列表: [3, 5, 6, 9, 10] 总重量: 33 最优解: 车A载重: 16吨 车B载重: 17吨 两车载重差: 1吨 车A装载的货物索引(从0开始): [0, 1, 3] # 对应重量 3, 5, 9 车A装载的货物重量: [3, 5, 9] 车B装载的货物重量: [6, 10]这个结果很有意思。总重33吨一半是16.5吨。我们找到了两个最优解一个是车A装16吨359车B装17吨610差值为1吨另一个是车A装17吨610不对6101635917差值为1吨。我们的算法找到了前者。两者的差值绝对值都是1都是最优解。这说明了问题可能有多解。关键点动态规划中的回溯路径可能不是唯一的我们的算法只找到其中一条。在实际应用中只要负载差最小任一方案都是可接受的。如果你需要所有最优方案则需要修改回溯逻辑记录所有可能路径这会更复杂一些。4.3 使用优化求解器OR-Tools快速验证对于习惯使用现成工具或者问题更复杂的同学也可以直接使用Google的OR-Tools这样的优化库。它内部封装了强大的求解器可以让我们更专注于建模。from ortools.linear_solver import pywraplp def balance_load_ortools(weights): 使用OR-Tools整数规划求解器 total_weight sum(weights) n len(weights) # 创建求解器 solver pywraplp.Solver.CreateSolver(SCIP) # SCIP是一个优秀的开源MIP求解器 if not solver: return None # 定义变量 x {} # x[i] 1 if item i goes to truck A for i in range(n): x[i] solver.IntVar(0, 1, fx_{i}) # 定义辅助变量 d 用于线性化绝对值 d solver.NumVar(0, total_weight, d) # 定义车A载重表达式 load_a_expr sum(weights[i] * x[i] for i in range(n)) # 约束d |2*load_a - total_weight| # 即 d (2*load_a - total_weight) 且 d -(2*load_a - total_weight) solver.Add(d 2 * load_a_expr - total_weight) solver.Add(d -(2 * load_a_expr - total_weight)) # 目标最小化d solver.Minimize(d) # 求解 status solver.Solve() if status pywraplp.Solver.OPTIMAL: load_a sum(weights[i] * x[i].solution_value() for i in range(n)) load_b total_weight - load_a indices_a [i for i in range(n) if x[i].solution_value() 0.5] # 由于是0/1变量0.5即视为1 return d.solution_value(), load_a, load_b, indices_a else: print(未找到最优解。) return None # 使用同样的数据测试 weights [3, 5, 6, 9, 10] result balance_load_ortools(weights) if result: min_diff, w_a, w_b, indices_a result print(f\nOR-Tools求解结果:) print(f 最小差值: {min_diff}) print(f 车A载重: {w_a}) print(f 车B载重: {w_b}) print(f 车A货物索引: {indices_a})OR-Tools可能会给出另一个最优解例如车A装[6, 10](16吨)车B装[3, 5, 9](17吨)同样差值1吨。这验证了我们动态规划解的正确性也展示了求解器的便捷性。5. 性能优化与问题变体探讨基本的动态规划解法在总重量T很大时会遇到性能瓶颈O(n*T)。在实际中我们可以根据情况采取一些优化和变通。5.1 针对大规模问题的优化思路Meet-in-the-Middle中间相遇法当货物件数n在30-40左右时子集总数2^n会爆炸但T可能也很大。此时可以将货物分成近似相等的两半。分别枚举前半部分和后半部分所有可能的子集和分别存入两个有序列表S1和S2。然后对于S1中的每个和a在S2中二分查找最接近target - a的值b使得ab最接近target。这样时间复杂度从O(2^n)降为O(2^{n/2} * log(2^{n/2}))对于n40是可行的。启发式算法与近似解当n和T都很大且对最优性要求不是100%时可以使用启发式算法。例如贪心算法降序排列将货物按重量从大到小排序依次将每件货物放到当前总重较小的那辆车上。这种方法速度极快但得到的往往不是最优解可能是一个不错的近似解。模拟退火或遗传算法将装车方案作为“个体”通过随机交换两车间的货物来产生新解并以负载差作为适应度函数进行迭代优化。这类算法可以在合理时间内为大规模问题找到一个质量很高的解。利用问题特性如果货物重量是整数且范围不大动态规划中的T虽然大但dp数组可以用位集bitset来压缩表示和加速运算。Python中可以用int的位操作来模拟C中可以用std::bitset能极大减少内存占用并利用CPU的位运算指令加速。5.2 常见问题变体及应对策略现实问题往往比教科书例子复杂。下面是一些常见的变体及思路调整车辆有载重上限这是更实际的情况。假设每辆车最大载重为C。此时约束变为W_A C且W_B C。目标可能变为在满足载重约束的前提下最小化|W_A - W_B|或者最大化两车的总装载量即最小化剩余货物。此时动态规划的状态定义需要改变dp[j]可以表示车A装载重量为j时是否可行j C。目标是在所有可行的j中找到使|2j - T|最小的那个T是已装货物总重可能小于总货物重因为有些货物可能装不下。车辆容量不同两辆车的最大载重分别为C1和C2。这时问题不对称了。我们可以定义决策变量x_i有3种状态0装车A1装车B2不装如果必须全装则没有状态2。目标仍然是最小化|W_A - W_B|但约束是W_A C1,W_B C2。这可以通过三维DPdp[i][w1][w2]解决但复杂度更高。更实际的方法是使用整数规划求解器。多辆车2问题迅速升级为多分区问题或装箱问题是NP-Hard的。通常采用启发式算法如首次适应递减法、最佳适应递减法等目标可能是最小化最大车辆载重Makespan或负载的方差。货物有装载顺序或兼容性要求某些货物不能放在一起化学物品或者必须按顺序装卸。这需要在模型中加入额外的约束条件例如如果货物i和j不能同车则添加约束x_i x_j 1如果货物i必须在货物j之前装车则可能需要引入时间变量问题会变成更复杂的车辆路径与装载混合问题。6. 实战避坑指南与经验分享理论完美实践踩坑。根据我处理这类问题的经验以下几个点是新手甚至老手都容易栽跟头的地方。6.1 数据输入的陷阱重量单位与精度这是最隐蔽的坑。如果你的货物重量是千克但车辆载重上限单位是吨直接计算就会出错。务必在计算前统一单位。更棘手的是如果重量是浮点数比如体积重量换算动态规划中的T和dp数组索引就不能直接用重量值了。解决方法有两种缩放取整将所有重量乘以一个倍数如1000转换为整数但要注意精度损失和可能导致的T过大问题。使用基于物品数的DP定义dp[i][j]为考虑前i件物品车A装载了j件物品时车A与车B的最小可能负载差。但这需要记录差值状态转移会更复杂。对于浮点数重量使用整数规划求解器通常是更稳妥的选择。6.2 动态规划中的“重复计算”陷阱在实现0/1背包类型的DP时内层循环必须从大到小遍历。这是关键# 正确做法 for j in range(total_weight, w - 1, -1): if dp[j - w]: dp[j] True # 错误做法会导致同一物品被无限次使用变成完全背包问题 for j in range(w, total_weight 1): if dp[j - w]: dp[j] True如果你发现求出的“最优解”中车A的载重竟然超过了总重量或者出现了不可能的组合99%是因为遍历顺序错了。6.3 回溯找方案时的路径记录正如我们代码中所示一维DP数组dp[j]只记录了可达性丢失了路径信息。为了回溯必须在DP过程中额外记录信息。我们代码中使用的prev_state字典是一种方法。另一种常见方法是使用二维布尔数组choice[i][j]表示在考虑前i个物品时重量j是否是通过选择第i个物品达到的。回溯时从choice[n][best_s]开始逆向推导。选择哪种方法取决于你对空间和代码清晰度的权衡。6.4 当“最优”不唯一时怎么办我们的问题可能存在多个最优解负载差相同。动态规划回溯找到的只是其中一条路径。如果你的业务逻辑对选择哪个解有偏好例如优先装重货、优先装某类货物你需要在回溯逻辑或目标函数中引入第二优化目标。例如在负载差相同的情况下最小化车A的货物件数或者最小化某类特殊货物的分布方差。这可以通过在状态中增加额外维度如物品件数或使用双目标优化方法来实现。6.5 从“两车”到“多车”的思想转变两车问题可以巧妙地转化为子集和问题。但一旦车辆变成三辆或以上这个技巧就失效了。多车均衡装载是一个完全不同复杂度的问题。此时不要试图去硬套两车的解法。正确的思路是将其建模为多分区问题或并行机调度问题目标是最小化最大车辆负载。常用的方法是整数规划/约束规划直接建模用求解器。列表调度启发式如LPT最长处理时间优先算法将货物按重量降序排列依次放入当前负载最小的车辆。元启发式算法如模拟退火随机交换不同车上的货物逐步优化。理解两车问题的本质是为了打好基础而不是用它去解决所有问题。认清问题的边界选择正确的工具是优化工程师的核心能力之一。这个两平板车装货的问题就像优化世界里的一个“麻雀”虽然小但五脏俱全。它涉及了整数规划建模、动态规划、回溯算法、精确解与启发式解的权衡以及从理论到实践的各种细节处理。下次当你遇到任何形式的“均衡分配”任务时不妨先想想这能不能抽象成一个“两分区”问题如果能那么今天讨论的这套方法或许就能成为你手中那把趁手的工具。