Доброго времени суток!
Студенчество миновало, а с ним и, уже давние, воспоминания о комбинаторике (за крайне редкой надобностью), к великому моему сожалению, испарились...
Так что прошу понять и простить в случае тугости понимания и реакции.

Суть проблемы: по движениям рег. Покупатели (ТиС) выбираем кред. документы реализаций и подбираем по максимуму товары <= Суммы движения.

Т.е. имеем некий частный случай задачи о рюкзаке, где:
вес - (Сумма-скидка)/количество
стоимость - отсутствует (ну, либо можно считать её равной весу)

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

Заранее благодарен!

ЗЫ: вариант с ДП 0-1 отбросил, т.к. преобразование результатов деления к натуральным числам дает кол*100000 предметов...
вариант с жадным алгоритмом - тоже...
---
Короче решения вот здесь, здесь и здесь.

Т.е.

```1c
    РюкзакПо(СуммаВсехЭлементов - ИскомаяСумма);
    //По полученному массиву:
    Для К = 1 По КолСтрВМассиве Цикл
    Таб.Кол = Таб.Кол - Таб.ВыбКол
    КонецЦикла;
```

Обработки вложил.
+ Можно добавить "жадину", чтобы гарантированно получать не менее оптимальные решения...

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

взято с инфостарта же
---
так это же, по-моему, и есть Динамическое Программирование 0-1.
Он не работает с вещественными весами (можно домножать до натуральных, но на моих выборках работает сие долго).
Или я ошибаюсь?

За ссылку спасибо! Сейчас почитаю.
---
где-то дома лежит рюкзак.ert , быстрее всех грызущий задачу по замерам 2004-5 года. Доберусь до дома, в личку стукну.
---
ок.
Заранее благодарен!
---
Пока вдохновляюсь вот этим перебором.
---
Вопрос актуален, но условия задачи изменились.
Рюкзак снизу не устроил.
Теперь необходимо набрать позиции на сумму большую или равную искомой, с минимальной разницей.

Т.е. на не меньшую требуемой.

ЗЫ: в ветке по линку обсуждение данной темы, но прийти к решению, в котором фигурирует количество, используя рекомендации пока не удалось.

По прежнему буду благодарен за помощь.
---
Короче решения вот здесь, здесь и здесь.

Т.е.

```1c
    РюкзакПо(СуммаВсехЭлементов - ИскомаяСумма);
    //По полученному массиву:
    Для К = 1 По КолСтрВМассиве Цикл
    Таб.Кол = Таб.Кол - Таб.ВыбКол
    КонецЦикла;
```

Обработки вложил.
+ Можно добавить "жадину", чтобы гарантированно получать не менее оптимальные решения...

ЗЫ: вознаграждение вернул, т.к. с момента объявления не было ни одного ответа.