Se o número de horas que cada pessoa está disponível for constante (por exemplo, sempre é de 1 hora), seu problema pode ser modelado como Fluxo de Rede , facilmente solucionável em tempo polinomial com o algoritmo de Ford-Fulkerson .
Para construir sua rede de fluxo, crie duas camadas de nós; a primeira camada representa suas bolas, a segunda camada representa seus baldes. Adicione uma aresta da fonte a cada bola com capacidade 1. Adicione uma aresta de cada bola a cada balde compatível com capacidade 1. Adicione uma aresta de cada caçamba ao tanque com capacidade correspondente à capacidade da caçamba. O fluxo máximo representa a atribuição ideal.
Caso contrário, se o número de horas que cada pessoa puder contribuir varia, o algoritmo acima não funciona devido à sua restrição de que cada pessoa pode visitar apenas um local. (O fluxo da rede resolveria o problema, mas poderia dividir as horas de uma pessoa em vários locais.) Nesse caso, você tem algo relacionado a um Mochila ou Problema de embalagem de caixa .
Se o número de horas que cada pessoa puder contribuir for um número inteiro, você poderá resolvê-lo por meio de programação dinâmica pseudo-polinomial. Caso contrário, você precisa:
- Implemente um algoritmo de retrocesso de força bruta. Isso fornecerá uma solução exata, mas não funcionará se o número de pessoas ou locais exceder 50 ou mais.
- Implemente um método heurístico combinatorial, como sugeriu Doc Brown. Hill Climbing ou Recozimento Simulado funcionará muito bem para este problema e fornecerá resultados ótimos ou quase ótimos muito rapidamente.