Задачка на подумать из практики

[g.Naukovych]

На прошлой работе в компании Manzanagroup у меня была следующая задача.
Мы делали программу лояльности.
Карты, баллы и прочее.

В лояльности существует группы баллов.
То есть за определенную покупку вы получаете баллы, соответственно правилам начисления.
Каждое правило начисляет баллы на определенную группу.
Таким образом у Вас получается баланс баллов, который разбит на сегменты.

Теперь мы хотим потратить баллы, но определенную группу можно списывать только на определенные товары.


пример.
купили сникерс и воду бонаква

баллы за сникерс можно тратить на любой товар, а баллы за бонаква только на бонаква.
Теперь я пришел еще раз в магазин и хочу снова купить сникерс и воду бонаква.
Но теперь хочу оплатить их теми баллами, что у меня есть.
Если я начну оплачивать воду бонаква, баллами сникерса, то я не смогу оплатить сникерс.

Теперь представим промышленный вариант, где групп баллов несколько и в чеке много позиций.
Вопрос, как расчитать, сколько максимально можно списать баллов?
Баллы всегда в целых числах и нельзя списать 1,5 балла или 1,10


или еще пример.

У нас есть матрица

NxM

где N кол-во позиций чека, а M группы баллов

если эту группу баллов нельзя использовать для этой позиции чека в матрице стоит 0.

во всех остальных ячейках у нас неизвестно.
И известно сумма для каждой позиции и общая сумма для всех групп баллов.


Цель заполнить матрицу так, чтобы сумма в каждой строке не должна превышать сумму группу,
сумма в каждом столбце не должна превышать сумма за позицию в чеке.
И цель сделать так, чтобы сумма всех элементов в матрице была максимальна.