Best approach to resource allocation problem 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.
Let us first show that your proposed greedy algorithm for the second restriction is not optimal.
For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $d_3 = 3$.
The greedy algorithm would assign $d_1$ and $d_2$ to the first city and $d_3$ to the second one, leading to only one city being retaken.
However, if we assign $d_2$ to the first city and $d_1$ and $d_3$ to the second one we could retake both of them and hence, the greedy algorithm is not optimal.
As for algorithmic approaches, note that your problem given the second restriction (let's denote it by $L$) is $\mathsf{NP}$-complete which can be shown by reducing $\mathrm{Partition}$ to $L$:
For a $\mathrm{Partition}$ instance given by a multiset $S$ of integers define an $L$-instance where the multiset of the $d_i$s is given by $S$, i.e. for every element of $S$ we create a team of the same size.
Denote by $X$ the sum of the elements of $S$ and set $e_1 = e_2 = X/2 - 1$ as well as $e_i = X + 1$ for all $i &gt; 2$.
Now note that we can retake at most $2$ cities (as we don't have enough forces to retake any city which is held by at least $X$ soldiers) and we can only retake both of them if we can split our forces exactly in half, sending $X/2$ soldiers to the first and second city, respectively.
It follows that $S$ is a yes-instance of $\mathrm{Partition}$ if and only if we can retake 2 cities in our constructed $L$-instance (I left out some technical details but this reduction should work out just fine).
Assuming $\mathsf{P} \neq \mathsf{NP}$ this result implies that $L$ has no (deterministic) polynomial time algorithm. For some further lower bounds, see the other answer.