C'è un algoritmo migliore per distribuire i valori da una sorgente a destinazioni X minimizzando la loro differenza?
Ho un numero intero sorgente. Ho bisogno di sapere quanto di quel valore ho bisogno di distribuire tra alcuni altri valori la proporzione di quella sorgente da distribuire tra gli altri ordinati interi per align renderli uguali il più possibile.
Example:
source = 20
destinations = [10, 20, 30, 40]
result should = [15, 5]
this will make final destinations look like [25, 25, 30, 40]Here the source "20" was divided among first 2 destinations in attempt to compensate their difference as much as possible. So the result is the list of integers: [15, 5].
Each destination has some common limit but it never overflows. If source value exceeds sum of destinations' "free room", than I just fill destinations up to it: sharing isn't needed. But if source is smaller then some sharing logic is needed.
# Other test cases (each destination's capacity is limited with 100):
# nothing to share:
share(0, [10, 20, 30, 40]) == []
# finally keeps dests the same: [10, 20, 30, 40]
# source exceeds total destinations' capacity (999 > 90+80+70+60==300)
# no special algo is required:
share(999, [10, 20, 30, 40]) == [90, 80, 70, 60]
# finally top-fills dests: [100, 100, 100, 100]
# source is smaller than first 2 items diffs (5 < 20-10=10)
share(5, [10, 20, 30, 40]) == [5]
# finally fills just the most poor dest: [15, 20, 30, 40]
# source is larger than first 2 items diffs (15 > 20-10=10)
# 1 indivisible point is left unshareable
share(15, [10, 20, 30, 40]) == [12, 2]
# finally fills 2 most poor dests also equalizing them: [22, 22, 30, 40]
# and so on...
Non riesco a capire meglio la denominazione e la descrizione di quel problema.
Ecco il codice in python che sono riuscito a implementare. Ma sento comunque la possibilità di un'idea migliore:
def share(available, members):
avail = available
imembers = iter(members)
member_ = next(imembers)
i = 1
distr = []
for member in imembers:
avail -= (member.value - member_.value) * i
if avail < 0:
distr = list(member_.value - imember.value for imember in members[0:i])
equal_share = int((source.value - sum(sharing)) / i)
distr = list(share + equal_share for share in distr[0:i])
break
member_ = member
i += 1
return distr
La soluzione finale / con l'aiuto di @Euforico
def diff(values, target):
# return the difference list of values and target
return [target - v for v in values]
def distribute(available, members, strict_equal=False):
# find across how many 'members' we must distribute 'available'
# and discover the total sum of those values
# in order to get diff list for them and the target value
total = available
idx = None
for idx, member in enumerate(members):
total += member
if idx >= len(members)-1 \
or total // (idx+1) <= members[idx+1]:
break
count = idx+1
dist = diff(members[0:count], total // count)
if not strict_equal:
for r in range(total % count):
dist[r] += 1
return dist