Finding optimal sequence of attacks to minimize number of soldiers needed

The problem

Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this:

You are given a list of enemy bases you want to conquer. You can only attack one base at a time. Each base $i$
requires a minimum number of soldiers $s_i$ to be conquered, will take out a
certain number $b_i$ of the soldiers who attack and will require a certain
number $r_i$ of soldiers to stay back holding it, as you move the remaining
army to the next battle.

The following relationship will always hold for a base $i$: $s_i \geq b_i$. Note that it is possible that $r_i \gt s_i$.

Determine the best sequence to follow in order to minimize the number
of soldiers needed to conquer all bases.

I know, given a certain order, how to compute the number of soldiers needed, and the solution space is finite, so brute-forcing it is always a possibility, but far from ideal. It looks like there is a greedy algorithm to find the right order.
My work
Finding the minimum number of soldiers needed for a given order

I found a series of inequations which I believe give me the number of soldiers $x$ needed to conquer and hold $n$ bases if attacked in from $1$ to $n$:

• We need enough soldiers to conquer the first base: $x_{a} = s_1$

• Before each subsequent battle, we need enough soldiers to take it after all the losses of the previous battles: $x_{b} = \max\limits_{2 \leq i \leq n} ( s_i+\sum\limits_{j=1}^{i-1}(b_j+r_j))$

• We want enough people to survive to be able to keep the last base:

$x_{c} = \sum\limits_{i=1}^{n}(b_i+r_i)$

So I believe the minimum number of soldiers needed $x$ to hold and retain all is $x = max(x_{a}, x_{b}, x_c)$. I think these equations can be used to prove that a certain order is optimal or not, though how exactly escapes me.
Finding the right order to minimise the number of soldiers needed

The key insights I figured out are:

• The army gets weaker with each battle, so the battles which re

Okay! In order to (hopefully) prove that your proposed greedy algorithm is correct, we will make an argument that is very common when dealing with greedy algorithms (as you can see from @D.W. 's linked question).

So, suppose you have found an $x$ such that there exists at least one sequence of battles where the army will survive. That is, there is some sequence of battles $\mathcal{B} = (s_1,b_1,r_1),\ldots,(s_n,b_n,r_n)$, such that we have $x \geq \sum_{j=1}^{i-1} (b_j+r_j)+s_i$ for all $i$ and also $x \geq \sum_{i=1}^n (b_i+r_i)$. Then we also have the sequence of battles given by your greedy algorithm: $\mathcal{B'} = (s_1',b_1',r_1'),\ldots,(s_n',b_n',r_n')$. And we want to show that if the army survives sequence $\mathcal{B}$, then they also survive sequence $\mathcal{B'}$.

To do so, we look at the smallest index $k$ where $(s_k,b_k,r_k) \neq (s'_k,b'_k,r'_k)$. Since these are just two different orderings of the same battles, there is some $t>k$ such that $(s_t,b_t,r_t) = (s'_k,b'_k,r'_k)$. Now, the idea is to change the ordering such that $(s_t,b_t,r_t)$ comes between $(s_{k-1},b_{k-1},r_{k-1})$ and $(s_k,b_k,r_k)$.

Now, what happens if the army does not survive this modified sequence? That means that there is some other index $i$ such that $x-(s_i+(b_t+r_t)) k$. From the way the battles were sorted in $\mathcal{B'}$, we therefore know that $s_t-(b_t+r_t) \geq s_i-(b_i+r_i)$. Reordering gives $s_t+(b_i+r_i) \geq s_i+(b_t+r_t)$. Putting it all together, we get this inequality: $x-(s_t+(b_i+r_i)) \leq x-(s_i+(b_t+r_t)) < \sum_{j=1}^{i-1} (b_j+r_j) \leq \sum_{j=1}^{t-1} (b_j+r_j)-(b_i+r_i)$.

This means that the army would not survive the original sequence of battles, $\mathcal{B}$! This calculation was derived from the assumption that the army did not survive the modified sequence; therefore that assumption must be wrong.

Now we know that as long as the chosen sequence differs from the greedy sequence at least at one point, we can just move the greedy choice to that point and still get a sequence where the army survives. Therefore the greedy sequence itself must always be among those where the army survives. Note that the trick with looking at the first index where the two sequences differ is a standard trick when proving greedy algorithms correct, and it is well worth it to familiarize oneself with this technique.

StackExchange Computer Science Q#165732, answer score: 3