Вход | Регистрация



Решение задачи жадного рюкзака

Решение задачи жадного рюкзака
Я
   Zhuravlik
 
31.03.18 - 03:37
Доброго времени суток) Обратился знакомый с вроде простой задачей - есть экселька на ~1000 строк с разными суммами, надо выбрать наиболее подходящие суммы к некоторой константной, которую вводит пользователь. Нашел пример решения полным перебором (от гения 1С) - но до этого я и сам практически дошел. А вот как это еще можно решать? К сожалению, математику совсем позабыл.. То, что в ютубе говорят в мозг не ложится. Может кто-то либо простым языком объяснить, либо дать пример решения?
 
 
   Zhuravlik
 
1 - 31.03.18 - 03:38
+ Полный перебор не катит - т.к. долго.. ФИФО не катит - т.к. неоптимально..
   Лодырь
 
3 - 31.03.18 - 04:14
а где мой коммент? или опять глючит
   Zhuravlik
 
4 - 31.03.18 - 04:15
Да вот тоже не увидел. Напиши еще раз?
   План Даллеса победа
 
5 - 31.03.18 - 07:40
> А вот как это еще можно решать?

1. Отсекай ветви.
2. Поставь удовлетворяющую точность.
3. Поставь ограничение по времени и по окончании бери самый удовлетворительный.
   Sammo
 
6 - 31.03.18 - 07:44
см. метод ветвей и границ
   План Даллеса победа
 
7 - 31.03.18 - 07:45
(4) Дай хотя бы самый общий анализ.

Если тебе надо набрать константу 100

А цифры из списка имеют значение в среднем 25-35, то это одно, а если цифры имеют значение 2-3 это другое.
   План Даллеса победа
 
8 - 31.03.18 - 07:46
(0) Можно расшифровать:
"наиболее подходящие суммы к некоторой константной"

Сумма чисел должна равнятся некой константе?
   Zhuravlik
 
9 - 31.03.18 - 10:03
(7) Задает например пользователь 2 миллиона. А числа - 35 тыс, 80 тыс, 219 тыс, 1,5 тыс и т.д. Вот среди них надо выбрать такие, которые в совокупности дают наибольшее / наилучшее приближение к этому числу.
Т.е. если по фифо - сортируем по возрастанию, и подбираем среди наименьших до тех пор пока их сумма не станет наиболее близка к критерию. Но в результате всегда будет остаток. Например если пользователь вбивает 11, а числа - 1,2,3,4,5,6... То ФИФО выберет 1+2+3+4. А надо 2+4+5.
   Zhuravlik
 
10 - 31.03.18 - 10:05
(6) Спасибо за совет, попробую покопать.. Вчера смотрел пару лекций - что-то вообще в голову не легло..
 
 Рекламное место пустует
   Garykom
 
11 - 31.03.18 - 10:07
(0) Задача распараллеливается?
   Zhuravlik
 
12 - 31.03.18 - 11:04
(11) не понял?
   Zhuravlik
 
13 - 31.03.18 - 11:05
А, нет.. Да как-то и не понимаю как ее можно распрараллелить.. Там же один рекурсивный цикл
   Сияющий в темноте
 
14 - 31.03.18 - 13:04
самый прос ой метод,случайный перебор
если сумма меньше,добавляем из тех,кл орые не включены,есдибольше,то удаляем любую мм,которые уюе включены и запоминаем минимал
   Aleksandr N
 
15 - 31.03.18 - 13:33
(0) Запросом?
   Garykom
 
16 - 31.03.18 - 14:34
(13) Чего там понимать то, последующие рекурсивные циклы запускаешь со 2, 3 и т.д. элементов.
Причем во всех циклах предусмотрено пропускать уже заюзанные начальные элементы.

Для 2 процессов:
1-й процесс цикл с 1-го элемента, пропускает 2-й, 4-й и 6-й и т.д.
2-й процесс цикл идет со 2-го элемента, пропускает 3-й, 5-й и т.д.

Причем пропуск (по условию) только на самом верхнем уровне, далее все элементы смотрит для выборки-укладки.
   Garykom
 
17 - 31.03.18 - 14:35
(16)+ Если хочешь решения задачки "очень быстро-быстро" то гугли OpenCL и CUDA.

Если готовы платить то могу наваять, видеокарту за 5 т.р. то надеюсь найдете ))
   Zhuravlik
 
18 - 31.03.18 - 16:22
(17) да ну, мне ж в 1С надо) ВК не умею) Скинул ветку знакомому, вернее знакомой, она может быть свяжется с вами, спасибо за предложение. Сам уже загружен другим, может позже как время будет поковыряюсь чисто для себя.
- Посмотреть "метод ветвей и границ"
- Подумать над возможностью вычислять рекурсию в параллельных потоках
   План Даллеса победа
 
19 - 31.03.18 - 17:45
(9)> Т.е. если по фифо - сортируем по возрастанию, и подбираем среди наименьших до тех пор пока их сумма не станет наиболее близка к критерию.

Глупость вот тебе надо 2 миллиона.

есть две цифры 500 000 и 1 500 000.

И есть циры 3.45, 7.89, 9.33

Тут неизвестно с каких цифр лучше начать искать.

И еще вопрос: а можно ли одну и ту же цифру два раза использовать?
   План Даллеса победа
 
20 - 31.03.18 - 17:50
(10) Обратись к классикам: http://algolist.manual.ru/maths/combinat/sequential.php
   ЕщеОдинПрограммист
 
21 - 01.04.18 - 00:35
Тут либо полный перебор, либо частичный. Полный даже с участием сортировки может быть не размно долго. А потому через генератор случайных чисел ищешь устраивающие варианты (подмножество вариантов из полного перебора), который гоняешь конечное время. И выдаешь тот из найденных, который лучше всего подходит. Главное определиться, что за критерий сравнения лучше-хуже.
   Zhuravlik
 
22 - 01.04.18 - 01:24
(19) ФИФО по твоему примеру возьмет 3.45 + 7.89 +  9.33 + 500 000. А жадный рюкзак как раз 500 000 и 1 500 000.
Сколько строк, столько и сумм. Если есть две строки по 10000 то можно два раза использовать 1000.
(21) Так нет четких критериев. Единственный критерий - итог подобранных сумм должен быть наиболее оптимален. Т.е. подобрать из наименьших так, чтобы приближение стремилось к 100% совпадения с исходной суммой.
   Zhuravlik
 
23 - 01.04.18 - 01:25
*Если есть две строки по 10000 то можно два раза использовать 1000. - опечатался. Если есть две строки по 10000 то можно два раза использовать 10000.
   Zhuravlik
 
24 - 01.04.18 - 01:34
Кстати, мб тут задачка по пределам?.. Функция от X стремится к числу..

lim F(x)
x->СуммаКритерия

Если понять что должно быть в F(x), и решить предел, то можно найти ту сумму критерия, которая будет максимально приближенным результатом.. Т.е. итог по совокупности из множества исходных сумм. Если ее определить, то жадный алгоритм будет работать быстрее, т.к. знаем к чему стремиться.
   Zhuravlik
 
25 - 01.04.18 - 02:23
Если предположить, что поиск должен быть по наименьшим\наибольшим суммам, то задача решается легко

&НаСервере
Функция ИндексыСуммПриближения(ТаблицаСумм, СуммаКритерий)
    
    ТаблицаПриближений = Новый ТаблицаЗначений;
    ТаблицаПриближений.Колонки.Добавить("Сумма", Новый ОписаниеТипов("Число"));
    ТаблицаПриближений.Колонки.Добавить("Отклонение", Новый ОписаниеТипов("Число"));
    ТаблицаПриближений.Колонки.Добавить("Индексы");
        
    ВГраницаСтрок = ТаблицаСумм.Количество()-1;
    
    Для СчетчикСтарта = 0 По ВГраницаСтрок Цикл
        
        СуммаКПогашению = СуммаКритерий;
        
        Приближение = ТаблицаПриближений.Добавить();
        Приближение.Индексы = ОбщегоНазначенияКлиентСервер.ЗначениеВМассиве(СчетчикСтарта);
        
        СтрокаСтарта = ТаблицаСумм[СчетчикСтарта];
        Для СчетчикПрохода=0 По ВГраницаСтрок Цикл
            
            Если СчетчикПрохода < СчетчикСтарта Тогда
                Продолжить;
                
            ИначеЕсли СчетчикПрохода = СчетчикСтарта Тогда 
                ТекСумма = СтрокаСтарта.Сумма;
                
            Иначе
                СтрокаПрохода = ТаблицаСумм[СчетчикПрохода];
                ТекСумма = СтрокаПрохода.Сумма;
                
            КонецЕсли; 
            
            Рез = МАКС(СуммаКПогашению, СуммаКПогашению - ТекСумма);            
            СуммаКПогашению = СуммаКПогашению - ТекСумма;            
            Если СуммаКПогашению <=0 Тогда
                Прервать;                
            КонецЕсли;     
            
            Приближение.Индексы.Добавить(СчетчикПрохода);            
            Приближение.Сумма = Приближение.Сумма + ТекСумма;
        КонецЦикла; 
        
        Приближение.Отклонение = СуммаКритерий - Приближение.Сумма;        
    КонецЦикла; 
    
    ТаблицаПриближений.Сортировать("Отклонение");
    СтрокаРезультат = ТаблицаПриближений[0];
    Сообщить("Отклонение по наименьшим = " + СуммаКритерий + " - " + СтрокаРезультат.Сумма + " = " + СтрокаРезультат.Отклонение);
    
    Возврат ТаблицаПриближений[0].Индексы;
    
КонецФункции
   ЕщеОдинПрограммист
 
26 - 16.04.18 - 22:06
(22)
> Так нет четких критериев. Единственный критерий - итог подобранных сумм должен быть наиболее оптимален. Т.е. подобрать из наименьших так, чтобы приближение стремилось к 100% совпадения с исходной суммой.

Как раз, наибольшее приближение к требуемой сумме, и при первом найденном равном остановить поиск - это четкий критерий. Тут нет понимания, сколько чисел может влезть в требуемую сумму. Там комбинаторный вопрос, объем вычислений которых возрастает факториально. Если до десяти штук - то обсчитать все пространство вариантов, если больше, то все зависит от ситуации. А дальше рекурсивный алгоритм перебора по сортированному списку чисел. Делал когда то, стоит дорого.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует