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

[Diman]

Классические задачи дискретного программирования
1. упрощенная задача о назначении целей (кол-во переборов уменьшено информацией о том, какие баллы к какой группе товара принадлежат). Решение в лоб: отсортировать товары по группам применимости баллов, сначала тратим спец баллы, потом обычные. Если речь идет об одном чеке.
2. при условии, что числа целые, это задача о ранце. Только добавятся итерации по подбору значений для каждой ячейки. Минус решения перебором большое кол-во итераций, но можно попробовать прикрутить метод приближения непрерывными задачами множителями Лагранжа, чтобы сократить кол-во итераций.
А как решали вы?