如何用动态规划求解这个背包？

Question

给定N对象(它们是1~n )，第一个对象的卷是ti和ti <= M；同时，有很多框，每个框的体积是M。现在，我们应该把所有这些对象放在盒子中，的顺序是1~N，应该使用多少个盒子呢？

例如，有5个对象，其体积为1~5阶的{7,2,5,3,9}，每盒的体积为10，因此最优解为3盒，它们分别为{7}，{2，5，3}，{9}。

我的解决方案：贪婪算法。假设第一个对象的最优解是x个盒子，剩余的空间是y，那么对于i+1对象，如果它的体积大于y，就必须将它放入另一个新的框中。否则，一个选项是将其放入当前框中，解决方案为(x，y-v)；另一个选项是将其放入另一个新框中，而解决方案是(x+1，M)。

问题：如何用动态规划解决它？

Answer 1

我不明白您为什么要使用DP来解决这个问题，因为您有一个非常好的贪婪的解决方案，但是下面是基于DP的想法：

让F(k)来回答第一个k对象--我们可以将它们放入的最少数量的框。让我们循环一下在最后一个框中放入多少个对象：

F(k) = min{F(l) + 1|l < k, t_(l+1) + t_(l+2) + .. + t_(k) <= M}
F(0) = 0

如果我们动态计算每个O(N*N)的t_i和，那么复杂性就是k。