物流装箱问题 -- 多重背包法

异想时刻

最近公司经常要往外发货，每次都要花一些时间计算如何更优地装箱，有时也会出现拆箱重装的现象，很是令人头疼。基于此，我便突发奇想设计一个算法来给出一些装箱参考方案。
物流发货时，我们需要同时考虑重量和体积，在箱子可承受的范围内尽量将箱子装满。鉴于此类应用场景，我们首先想到的可能就是背包问题，而且是多重背包。

假设:

N 为物品种类， W 为箱子承重， V 为箱子体积
对于每种物品,
数量 s_{i} , 重量 w_{i} , 体积 v_{i} ，价值 p_{i} ，其中， 0<=i<=N-1

如果依据多重背包求解的话，需要给出每件物品的价值。在实际物流发货操作中，要考虑运费成本，所以就要尽可能的将箱子装满而且箱数越少越好。这里我只单纯地优先考虑重量轻且体积小的物品装箱(如果有更好的方式欢迎讨论)，那么价值 p_i=1/(w_i*v_i) 。考虑到两个维度导致普通背包解法的时间复杂度 O(N*W*V*S) 会很大，单纯为了最优化装箱问题，这个解法在实际中带来的效益可能并不好，所以有必要进行优化降低时间复杂度。

单调队列

对于多重背包问题，除了基础动态规划解法(时间复杂度 O(N*W*S) )外，还有两种优化方式： 二进制优化(时间复杂度 O(N*W*log_{2}S) )和单调队列优化(时间复杂度 O(N*W) )。这里就不叙述二进制优化了，感兴趣可以了解下，是一种很巧妙的方法。而单调队列优化，顾名思义就是借助了特殊数据结构单调队列来优化多重背包问题。

单条件背包

众所周知，0-1背包的动态规划算式为 dp[i][w] = max\{dp[i][w], dp[i-1][w-w_{i}]+p_{i}\} ，那么多重背包就是在其基础上考虑物品数量，算式如下：

dp[i][w] = max\{
dp[i][w],
dp[i-1][w-w_{i}]+p_{i},
dp[i-1][w-2*w_{i}]+2*p_{i},
dp[i-1][w-3*w_{i}]+3*p_{i},
...,
dp[i-1][w-s_{i}*w_{i}]+s_{i}*p_{i}
\}

如果从背包容量的角度考虑(是不是就成了完全背包问题?！)，我们可以把上述公式转换为

dp[i][w] = max\{
dp[i][w],
dp[i-1][w-w_{i}]+p_{i},
dp[i-1][w-2*w_{i}]+2*p_{i},
dp[i-1][w-3*w_{i}]+3*p_{i},
...,
dp[i-1][w-k*w_{i}]+k*p_{i}
\}

将等式左右项的容量都加上 k*w_{i} ，可得到

dp[i][w+k*w_{i}] = max\{
dp[i][w+k*w_{i}],
dp[i-1][w+(k-1)*w_{i}]+p_{i},
dp[i-1][w+(k-2)*w_{i}]+2*p_{i},
dp[i-1][w+(k-3)*w_{i}]+3*p_{i},
...,
dp[i-1][w]+k*p_{i}
\}

如果为了方便计算，还可将其变换为

dp[i][w+k*w_{i}] = max\{
dp[i][w+k*w_{i}]-k*p_i,
dp[i-1][w+(k-1)*w_{i}]-(k-1)*p_{i},
dp[i-1][w+(k-2)*w_{i}]-(k-2)*p_{i},
dp[i-1][w+(k-3)*w_{i}]-(k-3)*p_{i},
...,
dp[i-1][w]
\}+k*p_{i}

显然， 0<=w+k*w_{i}<=W
进而可得， 0<=w<w_{i} , 0<=k<=(W-w)/w_{i}

可以看到，第 k 项的解其实与前 k 项有关。比如， w=0 时，即

0, w_{i} , 2*w_{i} , …, s_{i}*w_{i} , …, k*w_{i}

在此序列上各项的最优解只与其前面所有项中的最优解有关。所以我们只需要保存前 k 项的最优解，就可以快速计算出第 k 项的最优解，而无需逐项比较。那么此处就可以借助单调递减队列来保存前 k 项的最优解，其实就是队首 q_{h} 。
假设我们在队列中保存的是每项的 k 值，那么队首容量为 w+q_{h}*w_{i} ，其与第 k 项的容量之差 \delta_w = w+(k-q_{h})*w_{i} 。因此，我们可以得到如下两条结论:

若 k-q_{h}<=s_{i} , 则第 k 项还可以容纳 k-q_{h} 个物品i。
若 k-q_{h}>s_{i} , 则第 k 项还可以容纳所有物品i，即 s_{i} 。

这里我们来思考一个问题：在计算前 k 项的最优解时，是否需要遍历比较所有项呢？
毋庸置疑， k-q_{h} 为可容纳的物品i的个数。其范围为 0<=k-q_{h}<=s_{i} ，即 q_{h}<=k<=q_{h}+s_{i} ，最少容纳0个物品i，最多容纳 s_{i} 个物品i。所以，我们只需要考虑前 s_{i} 项即可。

至此，我们就得出了更新单调递减队列的两个条件了。

当第 k 项的解比队尾大时，队尾元素出队，直到队列中不存在比其小的项便将其入队, 保证了队列的单调性。
当 k-q_{h}>s_{i} 时，队首元素出队， q_{h}+1 入队。

在更新第 k 项的解时，只需与最优解队首元素 q_{h} 比较即可。

前面的分析是从重量的角度考虑，单从体积的维度考虑也是一样，这里不再赘叙。

多条件背包

那么，多条件的话该如何更新队列和最优解呢？
其实也并不复杂，只需同时考虑重量和体积两个维度即可。例如，当 w=0, v=0 时，

0 v_{i} … s_i*v_i … k_2*v_{i}
0 dp[i][0][0] dp[i][0][v_{i}] … dp[i][0][s_i*v_i] … dp[i][0][k_{2}*v_{i}]
w_{i} dp[i][w_i][0] dp[i][w_i][v_i] … dp[i][w_i][s_i*v_i] … dp[i][w_i][k_2*v_i]
… … … … … … …
s_i*w_i dp[i][s_i*w_i][0] dp[i][s_i*w_i][v_i] … dp[i][s_i*w_i][s_i*v_i] … dp[i][s_i*w_i][k_2*v_i]
… … … … … … …
k_1*w_{i} dp[i][k_1*w_i][0] dp[i][k_1*w_i][v_i] … dp[i][k_1*w_i][s_i*v_i] … dp[i][k_1*w_i][k_2*v_i]

由于要同时满足背包的承重和体积，所以队列中保存的值 k=min\{k_1, k_2\} 。每项的最优解为

dp[i][w+k_1*w_i][v+k_2*v_i]=
max\{dp[i][w+k_1*w_i][v+k_2*v_i], dp[i-1][w+q_h*w_i][v+q_h*v_i]+(k-q_h)*p_i\}

结论

虽然优化后算法的时间复杂度降了一个梯度，但计算时间仍然很长，毕竟实际箱子的承重( g )和体积( cm^3 )都很大。

后来转念一想，如果是为了将箱子装满，也没有必要采用如此复杂的算法。可以先考虑体积，再考虑重量。另外，为了尽可能同时达到箱子的承重和体积，那就可以优先考虑重量体积比 w_i/v_i 更接近箱子的重量体积比 W/V 的物品。由于重量体积比很似斜率，姑且就称其为“斜率法”吧。

算法
#算法 #多重背包
物流装箱问题 -- 多重背包法
https://r-future.github.io/post/tank-loading-solution-multi-entity-bag/
Author
Future
Posted on
November 12, 2021
Licensed under