How do we prove a method is optimal? This is a very simple question, infact it's so simple that I have no idea how to solve it.
We have an ordered list of $n$ words. The length of the $i$'th word is $W_i$.
Our goal is to write all the words in rows, such that no row can have a length of more than some value $L$.
1) We cannot rearrange the order of the words as they appear in the list.
2) $W_i < L$ for all $i$.
3) The length of a row is the sum of the lengths of the words written in that row.
Present a greedy algorithm to write all the words in rows that will minimize the number of rows. Prove it is the optimal solution.
So obviously the greedy method is "keep writing words until you can't fit any more words in that row. create another row and keep going." and it's clear to me why it is the best solution, but I can't seem to prove it. At best I can explain the intuition behind it but that is not a formal proof.
How do we write a formal proof that some algorithm is the best algorithm there is?
 A: For each row, the greedy choice is to select the "breakpoint" of the row as late as possible. So the last word in the first row will have length $W_k$, where:
$$
k = \max\{i \in \{1, \ldots, n\} \mid W_1 + \cdots + W_i \leq L\} \tag 1
$$
To prove optimality, it suffices to show two properties.

Greedy Choice Property: Consider an optimal solution $A$ that did not choose $k$ as the breakpoint, but instead chose some $j < k$. By taking the words of length $W_{j+1}, W_{j+2}, \ldots, W_k$ and moving them from the second row to the first row, we still obtain a valid solution:


*

*Only rows one and two are by affected by this change.

*By $(1)$, we know that row one did not overflow.

*The length of row two could only have decreased, and thus did not overflow either.


Hence, we obtain a solution that does make a greedy choice and is just as optimal as $A$.

Optimal Substructure Property: Let $A = \{k_1, k_2, \ldots, k_r\}$ be the breakpoints of an optimal solution that always makes the greedy choice to obtain $r$ rows, where $1 \leq k_1 < k_2 < \cdots < k_r \leq n$. Then we claim that $A - \{k_1\} = \{k_2, \ldots, k_r\}$ is an optimal solution for the subproblem of deciding where to put the breakpoints in the remaining list of words $W_{k_1 + 1}, W_{k_1+2}, \ldots, W_n$. Indeed, suppose instead that there exists some better solution $B = \{j_2, \ldots, j_s\}$ for this subproblem (so that $s - 1 = |B| < |A - \{k_1\}| = r - 1$). But then consider $\{k_1\} \cup B$. Since:
\begin{align*}
|\{k_1\} \cup B|
&= |\{k_1\}| + |B| &\text{since $k_1 < j_2$, the sets are disjoint} \\
&= 1 + (s - 1) \\
&< 1 + (r - 1) \\
&= r \\
&= |A|
\end{align*}
it follows that we have found a better solution for the original problem, contradicting the optimality of $A$. $\blacksquare$
