Доброго времени суток!
Студенчество миновало, а с ним и, уже давние, воспоминания о комбинаторике (за крайне редкой надобностью), к великому моему сожалению, испарились...
Так что прошу понять и простить в случае тугости понимания и реакции.
Суть проблемы: по движениям рег. Покупатели (ТиС) выбираем кред. документы реализаций и подбираем по максимуму товары <= Суммы движения.
Т.е. имеем некий частный случай задачи о рюкзаке, где:
вес - (Сумма-скидка)/количество
стоимость - отсутствует (ну, либо можно считать её равной весу)
В реализациях строк, как правило, не более сотни, но количества позиций могут легко переваливать за неск. тысяч.
Какой из методов лучше всего использовать, чтобы не словить минутный затык (желательно, чтобы не более пары секунд на больших доках работало) на 1с 7.7?
Заранее благодарен!
ЗЫ: вариант с ДП 0-1 отбросил, т.к. преобразование результатов деления к натуральным числам дает кол*100000 предметов...
вариант с жадным алгоритмом - тоже...
МассивВещей = Новый Массив();
КоличествоВещей = 100;
Для Х = 1 по КоличествоВещей Цикл
МассивВещей.Добавить(Новый Структура("Масса, Цена", СлучайноеЧисло(50), СлучайноеЧисло(1000) * 1000));
КонецЦикла;
// создадим двумерный массив (в принципе, это массив массивов, но мне лень это писать - поэтому сделал так )
А = Новый Массив(50, КоличествоВещей); // - = это псевдокод = -
Для Х = 0 по МассивВещей[0].Масса-1 Цикл
А[Х,0] = 0;
КонецЦикла;
Для Х = МассивВещей[0].Масса по 50 Цикл
А[Х,0] = МассивВещей[0].Стоимость;
КонецЦикла;
Для У = 1 ПО МассивВещей.ВГраница() Цикл // цикл по оставшимся вещам
Для Х = 0 по МассивВещей[У].Масса-1 Цикл
А[Х,У] = А[Х,У - 1]; // переносим предыдущие лучшие результаты для меньших масс
КонецЦикла;
Для Х = МассивВещей[У].Масса по 50 Цикл
А[Х,У] = Макс(А[Х,У - 1], А[Х - МассивВещей[У].Масса,У - 1] + МассивВещей[У].Стоимость); // помещаем тот результат, который оказался лучше
КонецЦикла;
КонецЦикла; // вещи
(2) так это же, по-моему, и есть Динамическое Программирование 0-1.
Он не работает с вещественными весами (можно домножать до натуральных, но на моих выборках работает сие долго).
Или я ошибаюсь?
Вопрос актуален, но условия задачи изменились.
Рюкзак снизу не устроил.
Теперь необходимо набрать позиции на сумму большую или равную искомой, с минимальной разницей.
Т.е. на не меньшую требуемой.
ЗЫ: в ветке по линку обсуждение данной темы, но прийти к решению, в котором фигурирует количество, используя рекомендации пока не удалось.