You have an array of floats, for example:
[74.45329758275943, 501.9063197679927, 172.59563201929095, 307.1739798358187, 362.042263381624, 940.1282277740091, 577.2604546481798, 63.201270419598224, 828.8081043649505, 31.1630295128974]
For each float, you can either call floor() or ceiling() to convert it to the nearest integer. The goal is to solve these two questions:
- Choose floor or ceiling on each float to produce a set of integers where sum(integers) = round(sum(floats)).
- Of the values that solve question 1, find the floor or ceiling choice that produces min(abs(float - int)), for each float/integer pair.
I think this is reducible to subset sum, and indicated as much during the quiz I just completed, but I wanted to check with people who have done reductions more frequently than me.
- Compute round(sum(floats) and subtract this value from each float in the array.
- Then for each of these "subtracted" floats, compute both floor and ceiling and put them in a new array with 2x the length of the old array.
- You now need to find a subset of these values, including both positive and negative integers, that sums to 0. However, you either need to choose the floor or the ceiling value for each of the original inputs, which limits the number of subsets that need to be searched.
I have not done an algorithms class in some time; is the analysis above correct, or am I missing something? Is this problem NP complete or is there a polynomial time solution?