0

The problem goes like this:

There are n piles of wooden planks and m machines, let xi be the number of planks in i-th pile. The machines produce different parts for chairs; each machine requires a different amount of planks, let's denote it by yj for j-th machine. To create a chair, you need one of each part.
You are given the task to assign the stacks to the machines - one machine can have many stacks assigned to it, but you can't split the stacks.
The question is: what's the most chairs you can make, given two arrays of integers - xi's and yj's (n>m)?

It sounds like a mix of knapsack problem and weighted subsets problem, so I think I won't be able to come up with an exact polynomial algorithm.

Brute force is out of question, because of amount of different solutions.

I guess I could easily use the simulated annealing approach to find a good approximation, starting with a random solution and moving the piles around.

What are your thoughts on this?

|improve this question
  • TBH unless it's a well-known problem or has a real-world application, you're likely to get a better answer on CS. There certainly seems to be quite a large class of various combinatorics problems that are close-but-not-quite what you describe. – Ordous Oct 25 '16 at 19:37
  • Thanks, I couldn't find stackexchange specifically for algorithms, for some reason I didn't think about computer science. I'll add this question there. – Solutus Immensus Oct 25 '16 at 19:47
  • If you took a look at the questions and answers there and you think it's going to be a better fit, then there is a function on the site to request a migration (you can find it under flag -> should be closed -> ...). It's kinda frowned upon to cross-post. – Ordous Oct 25 '16 at 19:51
  • please don't cross-post: cs.stackexchange.com/questions/65115/… "Cross-posting is frowned upon as it leads to fragmented answers splattered all over the network..." – gnat Oct 26 '16 at 6:41
1

The case m = 2, y0 = y1 = 1, is a well known NP-complete problem: Take a series of positive numbers (the xi) and divide it into two series, so that the sum of elements of the one series is as close as possible or equal to the sum of the elements of the other series.

On the other hand, you need not worry about this being NP complete, because the total "cost" of solving this problem would be the cost of the calculation, plus the cost of a huge number of wooden planks - so as long as the solution doesn't take long compared to the number of wooden planks, you are fine :-)

On the other hand, the solution might be polynomial in the number of planks, with the degree of the polynomial depending on the number of machines - if the solution time grows like a polynomial of degree 20, then it's not much fun.

If the number of chairs were allowed to be a real number, and the piles of planks could be split up, the solution would be easy - we add up the number of planks, and the total number needed for each chair, divide both sums to get the number of chairs that can be built (as real numbers) and divide the planks up accordingly. I would calculate that number first.

Let's say the calculation tells us we could hypothetically build 13.79 chairs. If that is the case, we determine whether we can assign piles to machines such that each machine has enough planks for 13 chairs; if that doesn't work then 12 chairs, etc.

To find if we can build k chairs, we need to assign piles of planks to machines, so that at least y0 * k planks are assigned to the first machine, y1 * k planks to the second, and so on. You might be able to solve this in reasonable time if the numbers are not too large; similar to the "first fit ordered" algorithm for bin packing:

To try to build k chairs, calculate how many planks each machine needs, sort the machines by planks in descending order. Sort the piles by number of planks in descending order. If there are k machines whose requirements can be fulfilled with the smallest k piles of planks then use those piles and remove machines and piles from the algorithm. Calculate how many "spare" planks you have. If the number is negative, try building k-1 chairs.

For the first machine: Add complete piles starting with the largest as long as this doesn't exceed the requirement. Then add the smallest pile that will meet the requirement for that machine if needed - but calculate how many unneeded planks you have, and if it exceeds the number of spare planks, you've failed. Then do the same with the second, third machine etc. Use backtracking when you fail.

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.