4. Cas complexe
Ici, on considère que la somme réclamée par les clients est la même que celle contenue dans les caisses. Si ce n'est pas le cas, on utilise l'algorithme vu dans la page précédente.
Prenons un exemple. Supposons que la banque possède 4 caisses de contenances respectives 30, 30, 60 et 40. D'autre part, 3 clients réclament respectivement 20, 60 et 80 pièces d'or. On obtiendra alors les attributions suivantes :
| Caisse | Client | Quantité |
|---|
| 0 | 0 | 20 |
| 0 | 1 | 10 |
| 1 | 1 | 30 |
| 2 | 1 | 20 |
| 2 | 2 | 20 |
| 3 | 2 | 60 |
Mais on aurait pu faire mieux si on avait mélangé autrement les clients et les caisses. Par exemple avec des caisses contenant 40, 60, 30 et 30 et des clients réclamant 20, 80 et 60, on économise une attribution :
| Caisse | Client | Quantité |
|---|
| 0 | 0 | 20 |
| 0 | 1 | 20 |
| 1 | 1 | 60 |
| 2 | 2 | 30 |
| 3 | 2 | 30 |
Posons n le plus grand entre le nombre de caisses et le nombre de clients (dans l'exemple précédent, on avait n = 4). Puisque les clients doivent être entièrement satisfaits et que les caisses doivent être entièrement vides, on voit bien que le nombre minimal d'attributions doit être égal à n.
L'algorithme d'allocation est le suivant :
# -*- coding: utf-8 -*-
def allocate(A, B):
allocations = []
a = 0 # indice dans la liste A
b = 0 # indice dans la liste B
qa = 0 # quantité déjà attribuée pour un élément de A
qb = 0 # quantité déjà attribuée pour un élément de B
while a < len(A) and b < len(B):
if A[a] - qa > B[b] - qb:
q = B[b] - qb
qa += q
qb = B[b]
else:
q = A[a] - qa
qb += q
qa = A[a]
allocations.append((a, b, q))
if A[a] == qa:
a += 1
qa = 0
if B[b] == qb:
b += 1
qb = 0
return allocations