I came up with a solution through dynamic programming.

The assumption is that each supplier's prices don't increase as the number of orders increases. Otherwise, it's nonsense, not suppliers.

The key observation is that if there is any answer (order distribution among suppliers), then among all active suppliers there is always one with the lowest current price. You can discount him the goods from the others, until we reach the limit of their price switching. In this case, the price of this vendor can also improve. The total amount of this will only improve. If you stumble on this vendor's supply, you can eliminate him from consideration and repeat the operation. Thus, only improving the answer, we will come to the fact that some suppliers sell their entire stock, some one sells some (and its price is less than all of the remaining). All of the remaining ones sell exactly the minimum amount for some price (the key from the input data). You can add option => to each vendor's price array, if it's not already there. And also write there 0 => 0 at the beginning (buy 0 for 0). Then everything is even simpler - all suppliers except one sell exactly some of their priceBreak pieces.

This simple reasoning tells us that we can look for the optimal answer only among those described above. Because any option can be reduced to this one, perhaps even improving it.

This can already be boiled down to something like the backpacking task. Go through one particular supplier (who will not sell a fixed number of pieces). Exclude him from the array of suppliers (but remember his prices so you can count how much he has to pay for the remainder).

Now, as in the backpack problem, consider DP(i,j) dynamic programming - what is the minimum price to get exactly i pieces from the first j customers (and each sells exactly some different priceBreak).

The base is trivial:

`DP(0,0) = 0, DP(i>0, 0) = infinity`

(in practice - a large number, or -1 and this value must be checked separately at the transition).

Transition:

`DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]`

Here we just go over how much the last supplier sells. We take the leftovers from the previous ones (DP(...,j-1) and add how much we pay to the last one.

There, you have calculated the DP. Now the answer is.

`min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i)`

. Go through how much you will buy from a special vendor. Take the rest from dynamic programming.

If there are M suppliers, we need to buy N pieces, each supplier has K prices, but this solution will be O(M*(M*N*K + N)) in time and O(M*N) in memory. (In fact, you can refine the time estimate- O(M*(M*N+N*L+N)), where L is the total number of entries in the price arrays of all suppliers).

To restore the answer together with DP(), remember which value of k gave the best result. Then you can unwind the optimal answer from the end, giving the known value to the last supplier.

If prices of suppliers can increase with increasing quantity, then the solution is still valid, but you should add to each array "quantity=>price" elements with quantity 1 less than each priceBreak. Because now in any answer, you can still flip from one customer to another, until either priceBreak from the top, or the last quantity with unchanged price. Again it turns out that only one vendor will sell a value not fixed in the array.

It is possible to bend the simplex method instead of the DP method, like

Philipp I have already written (it will be faster if there are few suppliers and the number of pieces is very large).

Maybe you can speed up the solution by M times, if instead of M different POs you make one with all suppliers. Then go through i<=n, distribute i pieces to suppliers taking only priceBreak, and then add the remainder to the supplier with the lowest price (without going over the next priceBreak!). But I'm not sure if this will work (I haven't been able to prove yet that if the optimal answer has the tail sticking out of priceBreak from some supplier, the answer will remain optimal for the new quantity).