Проблема рюкзака и 1с 7.7

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

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

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

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

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

ЗЫ: вариант с ДП 0-1 отбросил, т.к. преобразование результатов деления к натуральным числам дает кол*100000 предметов...
вариант с жадным алгоритмом - тоже...
По теме из базы знаний
Вознаграждение за ответ
Показать полностью
Найденные решения
8. Jill 17 28.06.17 13:14 Сейчас в теме +4 $m
Короче решения вот здесь, здесь и здесь.

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



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

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


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

За ссылку спасибо! Сейчас почитаю.
4. корум 287 16.06.17 15:26 Сейчас в теме
(3) где-то дома лежит рюкзак.ert , быстрее всех грызущий задачу по замерам 2004-5 года. Доберусь до дома, в личку стукну.
5. Jill 17 16.06.17 15:27 Сейчас в теме
(4) ок.
Заранее благодарен!
6. Jill 17 16.06.17 15:51 Сейчас в теме
Пока вдохновляюсь вот этим перебором.
7. Jill 17 27.06.17 15:35 Сейчас в теме
Вопрос актуален, но условия задачи изменились.
Рюкзак снизу не устроил.
Теперь необходимо набрать позиции на сумму большую или равную искомой, с минимальной разницей.

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

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

По прежнему буду благодарен за помощь.
8. Jill 17 28.06.17 13:14 Сейчас в теме +4 $m
Короче решения вот здесь, здесь и здесь.

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



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

ЗЫ: вознаграждение вернул, т.к. с момента объявления не было ни одного ответа.
Прикрепленные файлы:
Table.txt
ЛогикаПодбораСуммы_сверху_разница.ert
Оставьте свое сообщение
Вакансии
1С аналитик
Москва
зарплата от 210 000 руб.
Полный день

Руководитель направления 1С
Москва
зарплата от 350 000 руб.
Полный день

1С Программист
Москва
зарплата от 180 000 руб.
Полный день

Программист 1С
Москва
зарплата от 180 000 руб. до 220 000 руб.
Полный день

Аналитик 1С / Бизнес-аналитик
Нижний Новгород
зарплата от 100 000 руб. до 250 000 руб.
Временный (на проект)