[Haskell-beginners] Partition a number or optimize

[Animesh Saxena]

I did find a better solution but it’s still slow

let cities = 6
let clinics = 10
let populations = [1,10000,2,3,400,1]
let nparts n k = filter ((==n) . sum)  $ replicateM k [1..n]
let d2 = nparts clinics cities
let d1 = map maximum (map (\x -> zipWith (/) populations (map (\n-> fromIntegral n) x)) $ d2)
maximum $ zipWith (\n x -> (n `div` x) + (n `mod` x) ) populations $ d2 !! (head $ filter ((==minimum d1) . (d1 !!)) [0..])

here also nparts take time….if we choose clinics > 10

Heres the problem statement

The World Health Organization (WHO) wants to establish a total of B
vaccination clinics across Ncities to immunization people against
fatal diseases. Every city must have at least 1 clinic, and a clinic
can only vaccinate people in the same city where they live. The goal
is to minimize the number of vaccination kits needed in the largest
clinic. For example, suppose you have:

2 cities and
7 clinics to be opened.
If 200,000 is the population of the first city and
500,000 is the population of the second city, then
two clinics can open in the first city and
five in the second. This way,
100,000 people can be immunized in each of the two clinics in the
first city, and
100,000 can be immunized in each clinic in the second city.
So the maximum number of people to be immunized in the largest clinic is 100,000


-Animesh

> On Apr 27, 2015, at 10:19 PM, Ertugrul Söylemez <ertesx at gmx.de> wrote:
> 
> as 20, because it finds 2^19 partitionings.  You need to eliminate

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150427/cf27bc86/attachment.html>