Seeds distribution algorithm with complexity better than O(n^3)?

Question

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?

Answer 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.