Convoy Spare Capacity

Consider a conveyor belt on which many items are loaded. As the items come off the belt, they are loaded onto delivery trucks. All trucks are the same and they can carry items up to a specific maximum weight (called the capacity of the truck). Items are numbered from 1 and are of various weights. The items must be loaded sequentially onto the trucks, i.e., items 1 to N (for some N) go on the first truck, items N+1, …, M (for some M) go on the second truck, and so on. Not all trucks will be loaded to their full capacity, of course, but it is guaranteed that no single item is too heavy for a truck. We can load the trucks in a greedy manner (load as many items as you can on this truck and when the next item does not fit, start a new truck) but this may lead to an unbalanced distribution of the items among the trucks.

Define the spare capacity of the convoy as the sum of squares of the unused capacity of each truck in the convoy. We want to load the trucks in such a way to minimize the spare capacity of the convoy.

Given the capacity, c, of the trucks and sequence of weights of the items, how many items should each truck carry, and how many trucks are r开发者_如何学Goequired?

The first line of data gives the value of c and the number of items, n (<= 1000). Subsequent lines contain n values, the weights of the items, in order. Some sample data are:

6  5
1  2  3 
1  1

Output: on the first line, print the number of trucks required. On the second line, print the number of items on each truck, starting with the number of items on the first truck, followed by the number of items on the second truck, and so on. On the last line print the spare capacity of the convoy. For the above data, you should output:

2
2  3
10

Any ideas on how to solve this would be greatly appreciated.

---

Nice, whomever your lecturer or tutor is they have a sense of humour, they have given you a very hard problem to solve, infact it is NP-complete to solve exactly. This is an instance of the Knapsac Problem if I am not mistaken. Read the wikipedia page and alot of reasearch on it; there are plenty of algorithms out there that you can look at and implement that can be tailored to your exact problem space.