Предприятие, находящее в городе А, должно отправить потребителям в город В станки m типов. Вес одного станка i-го типа равен Gi тонн. Потребителями заказано Ni станков. За недопоставку станка i-го типа в установленный срок предприятие платит штраф Ri рублей. Железная дорога может предоставить предприятию транспортные средства общей грузоподъемностью Q тонн. Определить количество станков каждого типа, которые необходимо отправить потребителям, чтобы потери от неудовлетворительного спроса были минимальны?

Для решения данной задачи можно воспользоваться методом динамического программирования.

Пусть dp[i][j] - это минимальная сумма штрафов, которую предприятие должно заплатить, чтобы удовлетворить спрос потребителей на j станков типа i.

Изначально dp[i][j] = INF для всех i и j, кроме dp[0][0] = 0.

Затем для каждого типа станка i и каждого количества j от 1 до Ni пересчитываем dp[i][j] следующим образом:

dp[i][j] = min(dp[i][j], dp[i-1][j-k] + k*Gi + R), где k - количество станков i-го типа, которое мы отправляем, R - штраф за недопоставку.

Таким образом, после пересчета всех значений dp[N][Ni] будет содержать минимальную сумму штрафов, которую предприятие должно заплатить, чтобы удовлетворить спрос потребителей на Ni станков каждого типа.

Далее можно восстановить оптимальное количество станков каждого типа, проследив обратно по значениям dp.