这是一个双层背包问题,可以使用动态规划求解。首先将前三个货物(即 c1、c2、c3)装入第一辆车中,剩下的四个货物(即 c4、c5、c6、c7)再装入第二辆车中。此时,第一辆车的长度限制为 $L_1=1020$,第二辆车的长度限制为 $L_2=1020$,每个货物可以选择装或不装,即对应了一个双层 $0-1$ 背包问题。定义 $f(i,j,k)$ 表示前 $i$ 个货物中,第一辆车已装载了 $j$ 的物品长度,第二辆车已装载了 $k$ 的物品长度时,所能获得的最小浪费空间,则有状态转移方程:

$$f(i,j,k)=\min{f(i-1,j,k),f(i-1,j-l_i,k)+v_i,f(i-1,j,k-l_i)+v_i,f(i-1,j-l_i,k-l_i)+2v_i}$$

其中第一项表示不将第 $i$ 个货物装载;第二项表示将第 $i$ 个货物装载到第一辆车上;第三项表示将第 $i$ 个货物装载到第二辆车上;第四项表示将第 $i$ 个货物同时装载到第一辆车和第二辆车上。其中,$l_i$ 表示第 $i$ 个货物的长度,$v_i$ 表示其所占空间。

最终的答案即为 $f(7,1020,1020)$,即前 $7$ 个货物中,第一辆车已装载了 $1020$ 的物品长度,第二辆车已装载了 $1020$ 的物品长度时,所能获得的最小浪费空间。根据状态转移方程,可以使用三维数组进行动态规划求解,时间复杂度为 $O(nL_1L_2)$

数学建模两辆铁路平板车的装载问题问题描述:有两辆平板车其长度分别为 $L_1$ 和 $L_2$在装载时需要满足以下条件:1 货物必须全部装在车辆平台上;2 每辆车的长度限制不能超过 $L_1$ 和 $L_2$;3 货物在车辆平台上的位置必须尽可能地靠前离车头近;4 货物必须按照一定的顺序依次装载。假设有 $n$ 个货物需要装载每个货物的长度为 $l_i$问如何将这 $n$ 个货物分别装到这两辆车上

原文地址: https://www.cveoy.top/t/topic/euQ2 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录