Problem
The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city than the enemy, we retake the city. Our aim is to distribute our teams so that we maximise the number of retaken cities if:
- We can only place one team per city
- There is no limit to the number of teams we can play in each city.
Question
I'm trying to figure out which approach might be best for each option (greedy algorithm, divide-and-conquer, dynamic programming, backtracking). I'm not necessarily looking for the particular algorithm, although I'd be happy to get it too.
Previous work
One team per city
The best approach would be a greedy algorithm, which would assign to each city the smallest team which can defend it, starting from the smallest team. If at some point the smallest remaining team cannot take the smallest remaining city, we can simply dump that team.
No restriction for the number of teams per city
I can think of a greedy algorithm similar to the previous one, in which we assign the smallest teams to the smallest city until it's defended, and then move to the next one. However, I am not certain this would lead to an optimal solution, unlike the previous case. Backtracking explores the solution space exhaustively, so it would work but it's ineffective. Dynamic programming looks promising, as this superficially looks like a variation of the knapsack problem, but I know that generalisations/variations might not necessarily be tackled with the same approach.