Здравствуйте, ilnar, Вы писали:

I>а что если решить в терминах потоков? максимальный поток минимальной стоимости.
I>сходу не скажу, но похоже можно в ее терминах описать и решить соответствующими методами.

Задача NP-трудная. Здесь говорится, что найти "хоть какое-нибуть решение" можно с помощью эвристики:

The best fit decreasing and first fit decreasing strategies are among the simplest heuristic algorithms for solving the bin packing problem. They have been shown to use no more than 11/9 OPT + 1 bins (where OPT is the number of bins given by the optimal solution).[1] The simpler of these, the First Fit Decreasing strategy, operates by first sorting the items to be inserted in decreasing order by volume, and then inserting each item into the first bin in the list with sufficient remaining space. The sorting step is relatively expensive, but without it we only achieve the looser bound of 17/10 OPT + 2. A more efficient version of FFD uses no more than 71/60 OPT + 1 bins.[2][3] Recently, it was proved that the bound 11/9 OPT + 6/9 for FFD is tight.[4]

Although these simple strategies are often good enough, efficient approximation algorithms have been demonstrated[5] that can solve the bin packing problem within any fixed percentage of the optimal solution for sufficiently large inputs (this is called an asymptotic polynomial-time approximation scheme). This is an advantage the problem has over many other common NP-hard problems, some of which cannot be approximated within any constant factor at all.