车队备用容量

Question

考虑一条传送带，上面装载着许多物品。当物品从传送带上下来时，它们被装载到送货卡车上。所有的卡车都是一样的，它们可以运送的物品达到特定的最大重量(称为卡车的容量)。项目从1开始编号，并且具有不同的权重。物品必须按顺序装载到卡车上，即物品1到N(对于某些N)放在第一辆卡车上，物品N+1，…，M(对于某些M)上第二辆卡车，依此类推。当然，并不是所有的卡车都会满载，但可以肯定的是，没有一件东西对一辆卡车来说太重了。我们可以以贪婪的方式装载卡车(在这辆卡车上装载尽可能多的物品，当下一件物品不合适时，启动一辆新的卡车)，但这可能会导致物品在卡车之间的分配不平衡。

将车队的空闲容量定义为车队中每辆卡车未使用容量的平方和。我们希望以这样的方式装载卡车，以最大限度地减少车队的闲置容量。

给定卡车的载客量c和物品的重量顺序，每辆卡车应该运载多少物品，需要多少辆卡车？

第一行数据给出了c的值和项目数n (<= 1000)。后续行按顺序包含n个值，即项目的权重。以下是一些示例数据：

6  5
1  2  3 
1  1

输出:在第一行，打印所需的卡车数量。在第二行上，打印每辆卡车上的项目数量，从第一辆卡车上的项目数量开始，然后是第二辆卡车上的项目数量，依此类推。在最后一行打印车队的备用容量。对于上述数据，您应该输出：

2
2  3
10

任何关于如何解决这个问题的想法都将不胜感激。

Answer 1

很好，不管你的讲师或导师是谁，他们都很有幽默感，他们给了你一个很难解决的问题，实际上它是NP-完全的。如果我没记错的话，这是Knapsac Problem的一个实例。请阅读wikipedia页面并对其进行大量研究；有大量的算法可供您查看和实现，这些算法可以根据您的实际问题空间进行定制。