Задачка на подумать из практики
На прошлой работе в компании Manzanagroup у меня была следующая задача.
Мы делали программу лояльности.
Карты, баллы и прочее.
В лояльности существует группы баллов.
То есть за определенную покупку вы получаете баллы, соответственно правилам начисления.
Каждое правило начисляет баллы на определенную группу.
Таким образом у Вас получается баланс баллов, который разбит на сегменты.
Теперь мы хотим потратить баллы, но определенную группу можно списывать только на определенные товары.
пример.
купили сникерс и воду бонаква
баллы за сникерс можно тратить на любой товар, а баллы за бонаква только на бонаква.
Теперь я пришел еще раз в магазин и хочу снова купить сникерс и воду бонаква.
Но теперь хочу оплатить их теми баллами, что у меня есть.
Если я начну оплачивать воду бонаква, баллами сникерса, то я не смогу оплатить сникерс.
Теперь представим промышленный вариант, где групп баллов несколько и в чеке много позиций.
Вопрос, как расчитать, сколько максимально можно списать баллов?
Баллы всегда в целых числах и нельзя списать 1,5 балла или 1,10
или еще пример.
У нас есть матрица
NxM
где N кол-во позиций чека, а M группы баллов
если эту группу баллов нельзя использовать для этой позиции чека в матрице стоит 0.
во всех остальных ячейках у нас неизвестно.
И известно сумма для каждой позиции и общая сумма для всех групп баллов.
Цель заполнить матрицу так, чтобы сумма в каждой строке не должна превышать сумму группу,
сумма в каждом столбце не должна превышать сумма за позицию в чеке.
И цель сделать так, чтобы сумма всех элементов в матрице была максимальна.
|