两辆平板车货物装载优化：双层背包问题求解

这是一个双层背包问题，可以使用动态规划求解。首先将前三个货物（即 c1、c2、c3）装入第一辆车中，剩下的四个货物（即 c4、c5、c6、c7）再装入第二辆车中。此时，第一辆车的长度限制为 $L_1=1020$，第二辆车的长度限制为 $L_2=1020$，每个货物可以选择装或不装，即对应了一个双层 $0-1$ 背包问题。/n/n定义 $f(i,j,k)$ 表示前 $i$ 个货物中，第一辆车已装载了 $j$ 的物品长度，第二辆车已装载了 $k$ 的物品长度时，所能获得的最小浪费空间，则有状态转移方程：/n/n$$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/}$$/n/n其中第一项表示不将第 $i$ 个货物装载；第二项表示将第 $i$ 个货物装载到第一辆车上；第三项表示将第 $i$ 个货物装载到第二辆车上；第四项表示将第 $i$ 个货物同时装载到第一辆车和第二辆车上。其中，$l_i$ 表示第 $i$ 个货物的长度，$v_i$ 表示其所占空间。/n/n最终的答案即为 $f(7,1020,1020)$，即前 $7$ 个货物中，第一辆车已装载了 $1020$ 的物品长度，第二辆车已装载了 $1020$ 的物品长度时，所能获得的最小浪费空间。根据状态转移方程，可以使用三维数组进行动态规划求解，时间复杂度为 $O(nL_1L_2)$。