I have 27 hardwood flooring strips of varying lengths from 18 to 48 inches. I want to make 3 planks each consisting of 3 rows of flooring. Two planks have to be 60" long and another plank has to be 72" long. The total length of all the strips is enough to construct these planks. Obviously I could select the strips randomly, glue them up and cut them to size. However I would like to minimize the amount of cut waste.
The problem can be restated more simply as: I have 27 integers and would like to sort them into 9 sets. Each of 6 sets adds up to 60 and each of the remaining three sets add up to 72. This problem is a variation of the subset sum problem.
I found some posts discussing 'dynamic programming' but I know nothing of this approach let alone how to code it.
A similar problem was asked a while back but discussion is lacking.
My approach is the 'google way'. brute force. Compute everything. sort it out later. So,
group the integers into 9 arrays of 3 numbers.Note that there are 9!/3! = 60480 groupings.
for each group compute the sum of each array, call this the ArraySum. There are 9 of them.
(A,B,C,D,E,F,G,H,I)
compute the difference from the target sums (72,60,60)
A-72,B-72,C-72, D-60, E-60,...
add up all the differences for this group and store that number (call it GroupSum). This is the number I want to minimize.
Permute the pairwise differences between ArraySums and Target Sums gives (9!/3!=60480)
Now go back, change the grouping and repeat. I get 60480 x 60480 GroupSums = 3657830400
Sort the groupsums, find the lowest groupsum, choose that grouping.
Is there a better way than precomputing and sorting?
Unless I've misunderstood something, it seems irrelevant how you group them as long as you can find a grouping that works at all (i.e. where all the groups are at least the required length)
The logic being that you're starting with exactly the required amount of strips, meaning you're going to need to use all of them no matter what. The total length of strip you need is constant (60 * 6 + 72 * 3) and so is the total length you will use (whatever all your 27 sum up to), so the waste is a constant -- whatever the difference between them is. If I'm understanding right, a greedy algorithm should do the trick -- just use whatever combination gives you the minimum result for each given plank, resolving ties arbitrarily, and move on to the next.
Unless you want to minimize the amount of strips that need to be cut at all, i.e. allocate all the "waste" to as few strips as possible. In which case, you should use an L0 loss function, not L1 as you propose (i.e. you want to minimize the number of sums != 0, rather than the value of the sum itself)