The solution to this problem is in reducing it to the classical knapsack problem. Suppose the capacity of the knapsack is the duration of the concert, the objects are musicians, and the weights are the lengths of breaks. We want to distribute the objects into two sacks of equal capacity.

One way to do this is to fill one sack as much as possible and put all other objects in the other knapsack.

Once we've established which objects (musicians) go into which knapsack, the actual times can be obtained by having all musicians in the same knapsack take breaks one after another in any order.

We use dynamic programming to solve the knapsack problem. Let ~dp(P, W)~ be ~1~ if it is possible to find a subset of the first ~P~ objects such that their weights sum up to ~W~, and ~0~ if it is not possible.

The recursive relation for calculating ~dp(P, W)~ relies on observing the two options we have for using object ~P~, of weight ~w(P)~:

• If we decide that object ~P~ is not part of the subset (does not go in the sack), then we need to use some of the previous ~P-1~ objects to obtain the target weight ~W~. The expression ~dp(P-1, T)~ tells us exactly that.
• If we decide that object ~P~ is part of the subset (goes in the sack), then we need to use some of the previous ~P-1~ objects to obtain the weight ~W-w(P)~. The expression ~dp(P-1, T-w(P))~ tells us exactly that.