有一排的物品必须放在几辆卡车里给出了货物的重量、卡车的数量和它们的共同容量。物品只能从行的两端移到卡车上我们如何确定可以放置在卡车中的最大数量的物品？
（最多可以有10000件物品和100辆卡车。）
例子：
项目：（20、70、10、30、80、60、50、30）
卡车数量：3辆
载货量：100辆
在这里，我们最多可以放置7个项目，例如：
item to truck remaining
20 1 (70, 10, 30, 80, 60, 50, 30)
30 2 (70, 10, 30, 80, 60, 50)
70 2 (10, 30, 80, 60, 50)
50 1 (10, 30, 80, 60)
10 3 (30, 80, 60)
30 1 (80, 60)
60 3 (80)
我的想法是尽量给所有的卡车加满油，但包装问题对我来说是很新的，我对它们知之甚少。
最佳答案
这个问题确实可以通过动态规划来解决；但是如果没有以前的经验，这可能会很困难。递归关系和状态空间的定义如下。
设n表示物品数量，i_1,...,i_n表示其尺寸；设m表示卡车数量，c_1,...,c_m表示其容量。状态空间可以实现为m+2维表，其中位置(k_1,k_2,l_1,...,l_m)的条目被定义为从项目{k_1,...,k_2}（即项目的剩余队列）的补足中选择的最大可能的项目数，其中卡车k剩余的负载正好是cc>或否定的不存在这样的解决方案。在初始化与基本情况对应的状态之后，可以使用递归关系迭代计算状态空间。
(k_1,k_2,l_1,...,l_m) = max
{
(k_1+1,k_2,l_1,...,l_m),
(k_1,k_2+1,l_1,...,l_m),
(k_1+1,k_2,l_1-i_k_1,...,l_m) + 1, m cases in total
...,
(k_1+1,k_2,l_1,...,l_m-i_k_1) + 1,
(k_1,k_2-1,l_1-i_k_2,...,l_m) + 1, m cases in total
...,
(k_1,k_2-1,l_1,...,l_m-i_k_2) + 1,
}
如果前两个箱子对应于丢弃队列的左端和右端，则下一个箱子对应于将队列左端的物品打包到每个
l_k卡车，最后一个箱子对应于将队列右端的物品打包到每个m卡车。在评估状态空间之后，必须检查所有的结束状态；在这些状态中，每个项要么被打包，要么被丢弃这些状态是
m保持的状态，即队列将为空执行将采取这些的最大值；如果结果是负无穷大，则不存在可行解。