2

I have included my approach and solution. My solution works fine, however, is unoptimized with O(n^3) complexity

An NGO is running seed distribution program. It has limited quantity of varied quality seeds. In order to get seeds, farmer needs to request number of seeds. Seed distribution happens only on Sunday with goal that maximum farmers gets best quality seeds of same type.

Consider, NGO has following seeds and count (Ordered by quality - Top is highest):

|Quality|Fruit1|Fruit2|Fruit3|
|-------|------|------|------|
|Highest|     3|     3|     1|
|Medium |     2|     0|     0|
|Low    |     4|     0|     0|

Required Seeds:

  • Farmer 1: 2
  • Farmer 2: 3
  • Farmer 3: 1
  • Farmer 4: 2
  • Farmer 5: 3

Output: Goal is to assign highest quality seeds to maximum farmers.

  • Farmer 1: Highest Fruit1
  • Farmer 2: Highest - Fruit2
  • Farmer 3: Highest - Fruit1
  • Farmer 4: Medium - Fruit1
  • Farmer 5: Low - Fruit1

Here, farmer 1 and 3 in combination requested for 3 seeds, hence, in combination got highest fruit1.

My approach (Pseudocode)

I have a following domain classes - Farmer, , QualityType, FruitType, Seeds

QualityType has list of FruitType which has list of seeds.

To obtain result, I am doing following:

  • Iterate from highest Quality type to lowest.
  • nested iterate to fruit type and seeds.
  • For any seeds, check if we have farmer1 asking for same number of seeds - either alone or in combination with any one else.
  • If not move to farmer two.
  • This works however isn't optimized as it has 3 nested loops.

Can you please suggest any algorithm that can simplify it?

  • Can you give a farmer two different types (fruit or quality) of seed? – Ben Aaronson Jul 9 '15 at 14:42
  • No, if farmer requirement is more than seed of any type available, code should request him to reduce requirement. – JohncyWhack Jul 9 '15 at 14:46
  • what happens if 2 farmers ask for 3 seeds each, and you only have 5 available? – gbjbaanb Jul 9 '15 at 14:58
  • First come, first served – JohncyWhack Jul 9 '15 at 15:03
1

The best way is to divide the problem space first, so you only have to consider how many farmers want how many seeds of a particular fruit type and quality. You can do this in a single iteration. You need to know how many of each fruit and seed type is being requested.

Then divide the number of seeds of each quality by the desired number, rounding down, and assigning the remainder by giving 1 to the limited number of farmers. You can optimise this by determining the remainder as a fraction and giving the extra seed to that fraction of farmers (eg 7 seeds, 4 farmers = 1 1/3 seed each, meaning a farmer gets 1 less than what they asked for plus an extra 1 if the farmer counter <= 7 % 4. (although this breaks down if the fraction is less than 1 eg 4 seeds, 7 requested, in which case every farmer gets 0 seeds initially, the remainder is still allocated as before)

This makes it 2 iterations: 1 to build the set of farmers's requirements and another to fulfill them.

| improve this answer | |
  • Farmer doesn't specify fruity type or quality. Algorithm should try to award high quality seeds, while maintaining first cum first server. So if we have 6 seeds and first farmer asked for 6 and rest all farmers asked for 1, 3, 2.. Farmer 1 should get it as he asked first. However, in case farmers ask 1,6,3,2, in this case since Farmer 1 asked for 1, all farmer in combination i.e. 3 and 2 as well get 6 seeds. – JohncyWhack Jul 9 '15 at 15:31
  • then order the farmers in increasing numbers of seed requests (eg 1,2,3,6) and then do what I said above. – gbjbaanb Jul 9 '15 at 15:55

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.