I recently encountered this puzzle that seems like a standard combinatorial optimization or dynamic programming problem, but I wasn't able to crack it. I'm happy to receive answers, hints, references, or suggestions about related problems that I can map this one to.
Problem: You're out shopping for $N$ widgets. There are $S$ stores that carry the widgets, each having a stock of $N$ of them. However, each store has a different pricing scheme. For example, one store could charge \$1 for the first widget you order, but then the second widget could cost \$10 and the third only \$1. The cumulative order cost $f$ for this store has values $f(1) =1, f(2)=11, f(3)=12.$ The only restriction is that the cumulative order cost functions is positive on positive integers and strictly monotonically increasing. Having the $S$ stores' cumulative cost functions, (you can write capture all the relevant information in an $N\times S$ matrix, where each entry is positive and along each column the values strictly increase), you want to buy the $N$ widgets for the lowest possible price.
I imagine there's something better than the exhaustive search over all ${\tbinom {N+S-1}{N}}$ possible ways. I tried looking at marginal costs and then doing a greedy approach but this doesn't work.
As a possible extension: what happens if you decide you want more than $N$ widgets?
I think dynamic programming works. For $n=1,2,3,\dots,N$ determine the cheapest way to buy $n$ widgets from stores $1$ and $2$, and store the results. With this in hand, it's straightforward to determine the cheapest way to buy $n$ widgets from stores $1,2$,and $3$. For $k=1,\dots,n$ compute the cost of buying $k$ widgets from store $3$ and $n-k$ widgets from stores $1$ and $2$, and store the least expensive method and its cost.
Then add stores $4,5,\dots,S$ in the same manner.
While this will be better than trying every possible combination, it still seems very computationally demanding.
I think one might be able to make some performance gain if it were true, in contrast to your example, that the $n+1$st widget was never more expensive than the $n$th widget, from any given store. That's just a guess though. I haven't really thought about it, since you say the assumption doesn't hold.