Algorithm problem

Question

Hello all!

I have a bit of a problem with the algorithm proposed as homework by our teachers. It goes something like this:

Having a number of sticks like so:

4 (the number of piles to use)

11 7 5 4 (length of the sticks)

1 1 3 3 (how many sticks per length)

I have to figure out an algorithm that will form the minimal number of sticks by merging them. The solution for the previous example is this:

15 3 (15(optimal sum) * 3(minimal sticks) = 45 = 11*1 + 7*1 + 5*3 + 4*3)

11 4

7 4 4

5 5 5

Now I am not asking for you guys to solve this problem, but to give me a line to follow, I have tried to reduce it to a "Make Change" problem, it went good until the part where I had to select from the remaining solutions the good ones.

The complexity desired is an exponential one and the restrictions are:

1. 0 < sticks < 100
2. 0 < max_sum_of_sticks < 1000

So do you guys have a second thought on this?

Thank you very much for your time.

Explanation on minimal number of sticks : if for instance i had a set of sticks. The sum to be formed is 80, i have a fair amount of solutions :

1 stick of length 80

2 sticks of length 40

4 sticks of length 20 so on.

The first one is trivial and we discard it,for the remaining solutions I have to test if I can build them with the sets of sticks I have because there is a possibility that the solution chosen, for example 2*40, isn't a reliable one because we have sticks that were not used.

Answer 1

This looks a lot like the Knapsack problem.

You might also take a look at Branch and bound, which is a general algorithm for all kinds of optimization problems.

Answer 2

I am not sure I understand the problem.

• I assume each pile has to be the same length? That is, the sum of length of sticks has to be same in all piles?

• We have here three piles. Where did this three come from? If it were possible to make 2 piles, which one would you choose? For example, if you only have six sticks of X length, would you make three piles each with two sticks or two piles, each with three?

I guess the brute force methods is: you try to make X piles. Put all permutation/combination in each pile and see if you end up with the same total length in each.

Would it help if you give unique names to each stick? In this case, you have 11-1, 7-1, 5-1, 5-2, 5-3, etc.

Answer 3

Like Julian, I'm not entirely sure what you mean, but it sounds a lot like the "Knapsack Problem" over multiple knapsacks, and is NP-complete. There are many different ways of approaching it - from the simple heuristics like "use the big stuff first", down to ant-colony (genetic) optimisation. And almost everything in between.

In fact, there are almost as many approaches as there are candidate sets... I wonder if the question is NP-complete? ;-p

Answer 4

Note: I'm calling merged sticks "piles" in this answer.

Of course, the solution is always "1". Merge all of your sticks into one big pile; you have optimal sum = total length of all sticks and minimal piles = 1.

Now, assuming you want the next smallest number after 1, there are a few feasible options. Would you try 2 minimal piles? Why not? What about 4? 5?

Let's say you are left with two candidates, 3 and 5. (i.e. optimal sum=15,minimal piles=3 and optimal sum=9,minimal piles=5) If you know you can arrange your sticks into 3 piles of length 15, do you need to check 5 piles (and what length would they be)?

So, the problem comes down to finding whether you can arrange your sticks into m piles of length n.

I'm sure there's a lot of literature on this problem, but if I were doing it for homework, I'd start by solving it on my own.

And I would start by trying to form one pile of length n. Then trying to form m-1 piles of length n with the remaining sticks...

The thing to be careful about with this approach is that you may form a wrong pile at any given time, so you'd need a way of backtracking and trying another combination. For example, suppose we have these sticks: 20 1 7 7 7 7 14 6 15 and are trying to form 4 piles of length 21. This is possible with the combination (20 1) (7 7 7) (7 14) (6 15), but if you start with (14 6 1), there's no solution that will give you 3x21 piles for the rest of the sticks. Now, I'm not sure if this indicates that 4x21 is not the answer. (The answer is, in fact, 2x42.) If that were the case, you would not run into this problem of "wrong" piles if you always started with the smaller number, i.e. tried 2x42 before trying 4x21. However, not being sure, I'd write code that would backtrack and try all the different combinations before giving up.