0

What would be the best algorithm to solve this problem? I spent a couple of hours on this problem. But couldn't sort it out.

A guy purchased a necklace and planned to make it into two pieces in such a way that the average brightness of each piece should be either greater than or equal to the original piece.

The criteria for dividing the necklaces are

1.The difference in number of pearls between the two pearls sets should not be greater than 10% of the number of pearls in the original necklace or 3 whichever is higher.

2.The difference between number of pearls in 2 necklaces should be minimum.

3.In case if the average brightness of any one of the necklace is less than the average brightness of the original set return 0 as output.

4.Two necklaces should have their average brightness greater than the original one and the difference between the average brightness of the two pieces is minimum.

5.The average brightness of each piece should be either greater than or equal to the original piece.

eler
  • 3
  • 1
  • Tell us how you are measuring "brightness" because the canonical way of computing an average would make it impossible for the average of the averages of the partitions to be greater than the average itself. Furthermore, if one part is higher than the original average, the other part must be lower -- that is, you must divide the necklace exactly in half to achieve the results you're seeking. – Kaganar Mar 30 '12 at 20:15
  • @Kaganar - The input values will be a set of numeric numbers, eg -{10,6,3,9,7,2,5,8,4,1} where 0 ≤ brightness ≤ 10. – eler Mar 30 '12 at 20:19
  • And you're planning on breaking that set up into two parts such that the average of each part is equal to or greater than the average of the original set? – Kaganar Mar 30 '12 at 20:20
  • @Kaganar - yes. Exactly. But the number of pearls in the subsets could vary. – eler Mar 30 '12 at 20:25

1 Answers1

0

This problem is rather hard to do efficiently (in NP somewhere).

Say you had a set that averaged to X. That is, X = (x1 + x2 + ... + xn) / n.

Suppose you break it up into sets that average to S and T with s and t items in each set, respectively.

You can mathematically prove that if one of the averages, S or T, is greater than X, the other of the two must be less than X.

Hence, the two sets must have exactly the same brightness because that's the only way your conditions are satisfiable.

Knowing this, you're ending up with the sumset sum problem -- you want to find a subset that sums to exactly half of the sum of the entire set. That's a problem that's known to be hard. (It's been classified NP. And alright, it's not exactly the same as the subset sum problem, but if subtract the average of the full set from each of the brightness values, solving the subset sum problem will give you your answer. (Do the reverse to see how you can solve the subset sum problem from your problem.)

Hence, there's no fast way of doing this -- only approximations or exponential running times... However, maybe this will help. It mentions better running times if your weights (in your case, brightness levels) are bounded.

Community
  • 1
  • 1
Kaganar
  • 6,540
  • 2
  • 26
  • 59
  • Thanks for your great help. I will dig into it and let you know. – eler Mar 30 '12 at 20:46
  • Let me brief what i understood. First of all we need to find a subset using sumset sum. Then subtract the average of the full set from each of the value in the subset. Am I going in right direction? – eler Mar 30 '12 at 21:42
  • Sorry for the delay.. And sort of, but in the other order.. First, subtract the average from each brightness level and then solve the subset sum problem. Then whatever set sums to zero is one half, and the rest of the set is the other. (Incidentally, both the sets should sum to zero.) – Kaganar Apr 02 '12 at 17:09