Есть ТЗ:

Док1 1000
Док2 15,5
...

Нужен алгоритм набирающий под определенную сумму документы (чем ближе будет сумма тем лучше).
Никто ничего подобного не встречал?

неа, я сегодня голову освежиться отправил....

ну блин, считай модуль от разности...
а нах тебе?:

http://books.sakhgu.sakhalin.ru/Volume%203/%d0%a1%d0%a2%d0%9e%d0%a5%d0%90%d0%a1%d0%a2%d0%98%d0%9a%d0%90/%d0%9a%d0%bd%d0%b8%d0%b3%d0%b8%20%d0%b8%20%d1%81%d1%82%d0%b0%d1%82%d1%8c%d0%b8%20%d0%bf%d1%80%d0%be%d1%84%20%d0%9e%d1%80%d0%bb%d0%be%d0%b2%d0%b0/%d0%9c%d0%b5%d0%bd%d0%b5%d0%b4%d0%b6%d0%bc%d0%b5%d0%bd%d1%82%20(%d0%ba%d0%bd%d0%b8%d0%b3%d0%b0)/3-2-%d0%9c%d0%b5%d1%82%d0%be%d0%b4%d1%8b%20%d0%be%d0%bf%d1%82%d0%b8%d0%bc%d0%b8%d0%b7%d0%b0%d1%86%d0%b8%d0%b8.rtf

ниче так сцылка...

(0) "Задача упаковки рюкзака". Оно?

(0) вот, например
http://algolist.manual.ru/maths/combinat/index.php

(4) %) "Проверено - вирусов нет"
+(3) = методы оптимизации

(2)Модуль от разности?! - че ето значит? Просто нужно перекинуть доки на опр. сумму с одного контрагента на другого

ТЗ
Сортировать
Перебор

Нужен алгоритм набора нужной суммы

Я сегодня не в форме. чисел не много:
6363,01
214105,12
38155,00
2610,00
763146,69
25290,00
36440,00
90510,01
10400,00
83649,08
140845,04
17918,46
388555,66
233882,85
85708,17

нужно составить как можно ближе 990145,60. Методом тыка я составил число 990261,81. разница - 116,21.

Если кому интересно, то поможите пожалуйста

тебе ж уже сказали, куда двигатся, товарищ!!!.. это задача оптимизации..

(14)Ладно буду вкуриваться:(

(15) Блин ну и сделай их в виде цикла
1+2+3+4+5 пока <>10000
1+2+3+4+6 и тд

мда... ЧМы рулят... Комбинаторика + функции распределения + ЧМы.

(17)кто такие ЧМы?

(16)Я даже не могу просчитать сколько потенциально может быть комбинаций. Порядок не принципиален, число слогаемых тоже.

(18) Чемпионаты мира (Численные Методы).
(0) ищи в яндексе "NS рюкзак"

(19) Рекурсию смотри - когда мало сумм порядка 10 то можно методом перебора взять

1    2    3    
           
1    12    123    
2    13        
3    23        
           

1    2    3    4
           
1    12    123    1234
2    13    124    
3    14    134    
4    23    234    
   24        
   34            

1    2    3    4    5

1    12    123    1234    12345
2    13    124    1235    
3    14    125    1245    
4    15    134    1345    
5    23    135        
   24    145        
   25            
   34            
   35

Составил себе табличку с вариациями. Буду теперь думать

(23) А чего думать то? Алгоритм есть с кодом в (10) посте ....

Я запарился читать. А тут я вижу уже закономерности для циклов

Спасибо за ссылки.
Вскорости буду писать заполнение палеты не больше заданного объема...

Я сделал это сам:)))))) Проверяйте. Что скажете про алгоритм?

http://moy1c.narod.ru/Downloads/FindSumm.ert

Блин... Ты-б еще похвастался своим первым сексуальным опытом...

(28)Первый сексуальный опыт по сравнению с этим ничего особого

Алгоритм полностью свой. Ссылки что сдесь смотрел нифига не вкурил

все не читал но вроде что то связаное с транспортнойц задачей...де то встречал на проклабе что ли что то подобное

ХЗ - транспортную задачу списал в свое время. Выложил в екселе свою закономерность

Начинай с большей, добивай меньшими

Вряд ли это мое ноухау. Но вот табличка объясняет алгоритм

1                        
   2                    
       3                
           4            
               5        
                       
   12    13    14    15        
       23    24    25        
           34    35        
               45        
                       
       123    124    125    134    135
           234    235    245    
               345        
                       
           1234    1235    1245    1345
               2345        
                       
               12345

Сколько чисел столько и обходов. В каждом обходе добавляем оконцовку из предыдущего обхода

(29) Мне тебя жаль... Искренне жаль...

(36)Всему свое время. Нельзя все время о сексе да о сексе

UP.Что никто не хочет обсудить?

(38) Нет, что тут обсуждать?
Мне стыдно.:( Но у меня  под сумму, последовательно документы подбираются.
Как набрали - так стоп. Последний документ - юзер сам сам подбирает/удаляет. Может вообще все руками набрать, если ему угодно.
Знаю, что тупо - зато давно работает.:)

(38)
Симплексом пробовал решать?

(40)Нет. Можно ссылку - как это?

1. Симплекс не поможет - всегда разницу будет давать 0 (если сумм документов хватает, чтобы покрыть нужную сумму).
2. Рюкзак ближе, но тоже бесполезен по 2-м причинам: 1) нет ограничения, что сумма не превышает заданной (это можно было бы обойти) 2) схемы неявного перебора (ветвей и границ), которые хорошо работают в рюкзаке не дадут здесь сокращения перебора, т.к. релаксированная задача (можно брать не полностью сумму документа, а часть) всегда будет давать разницу = 0 и отсечения ветвей не получится.
3. Схемы неявного перебора - см п.2.
4. Я бы посоветовал попробовать, как Вы поступали в приведенном примере ("жадный" алгоритм):
- упорядочить суммы по убыванию;
- набрать документы в порядке убывания не превышая сумму. Зафиксировать отклонение как рекорд. Пройтись по документам ниже, вычисляя, что получится, если документ будет включен. При этом, если результат (отклонение от заданной суммы) лучше рекорда, то это текущий рекорд.

(41) Ищи книгу Хемди А. Таха "Теория оптимизации" - на мой взгляд лучше ничего нет.
(42) Предположим имеем
Документ | Переменная | Сумма
-----------------------------
№ 1      | x1         | 1000
№ 2      | x2         | 500
№ 3      | x3         | 600
№ 4      | x4         | 800
№ 5      | x5         | 900

Нужно набрать сумму 2000 или сумму наиболее близкую к этой.
Тогда имеем две подзадачи:
1.
максимизировать 1000*х1 + 500*х2 + 600*х3 + 800*х4 + 900*х5
1000*х1 + 500*х2 + 600*х3 + 800*х4 + 900*х5 <= 2000
При х1..х5 <=1 и х1..х5 - целые
2.
минимизировать 1000*х1 + 500*х2 + 600*х3 + 800*х4 + 900*х5
1000*х1 + 500*х2 + 600*х3 + 800*х4 + 900*х5 >= 2000
При х1..х5 <=1 и х1..х5 - целые

Получается две подзадачи, каждая из которых представляет из себя задачу рюкзака, на которой хорошо работает схема "Ветвей и границ".

Решаем задачи и выбираем наименьшее отклонение.

(43) + И если после первой подзадачи отклонение равно нулю - тогда вторую подзадачу не решаем.

(44)Обработку можешь сделать?

(45) Мне сейчас некогда. Напомни о себе недели через две-три - я сделаю.

(46) + только ты книгу, которую я в (43) указал почитай, иначе все равно ничего не поймешь.

(46)Вспомнишь сделай, не вспомнишь пох. Просто я не понял (43)

(47)Попробую завтра

(43) Схема ветвей и границ в этих задачах будет неэффективна, т.к. не будет происходить отсечения "неперспективных" ветвей из-за совпадения коэффициентов ограничения и функционала.

(50)Ничего не понял, но звучит убедительно

(50) А можно поподробнее с этого момента. Почему при совпадении коэффициентов не будет происходить отсечение неперспективных ветвей?

Как правило, для оценки "перспективности" ветвления используют задачу линейного программирования, т.е. снимают условия целочисленности (релаксация для краткости). В вашем случае решение релаксированной задачи всегда (почти) будет давать отклонение = 0 из-за того, что всегда есть возможность добавить часть суммы документа до заданной суммы. Т.е. нельзя будет отсечь никакую ветвь путем сравнения уже имеющегося рекорда с оценкой, полученной в релаксированной задаче.

(53) Это справедливо для задач, где есть дополнительные условия? Например для такой:

максимизировать 1000*х1 + 500*х2 + 600*х3 + 800*х4 + 900*х5
1000*х1 + 500*х2 + 600*х3 + 800*х4 + 900*х5 <= 2000
х1 + х5 = 1
х2 + х4 = 1

При х1..х5 <=1 и х1..х5 - целые

Вот пример задачи о ранце, где схема ветвей и границ не дает сокращения перебора.
X1+X2+...+Xn <= n/2+0.1
X1+X2+...+Xn -> MAX
Релаксированные задачи будут давать оценку (сверху) =  n/2+0.1, а рекорд - n/2.
Поэтому схема ветвей и границ переберет не менее С(n, n/2) (число сочетаний из n по n/2) решений. А это много (2^n/SQRT(2*Pi*n)).

(54) И для такой задачи - тоже: x5 и x4 можно просто исключить.
Грубо говоря, схема ветвей и границ в задаче о ранце эффективна, когда векторы ограничений и функционала неколлинеарны.

Напоследок: может пригодится такой подход.
Пусть есть линейная форма (A,X) = A1*X1+...An*Xn, Xi={0,1}
Расмотрим функцию: F(X) = (1+X1^A1)*(1+X2^A2)+...+(1+Xn^An).
Функция F(X) - производящая для числа решений уравнения (A,X)=b, т.е. если F(X) привести к нормальному виду - раскрыть скобки и привести подобные члены, т.е. к виду F(X) = СУММА(Cb*X^b), то Cb - число решений уравнения (A,X)=b. Например, для линейной формы X1+...Xn производящая функция = (1+X)^n и это полином с биномиальными коэффициентами. Для обсуждаемой задачи использование производящей функции может быть эффективнее перебора, если разных значений сумм документов значительно меньше 2^n. Получив производящуб функцию в нормальном виде и упорядочив ее коэффициенты легко найдем нужное решение - это
коэффициенты, соседние с требуемой суммой.
Собственно решение можно получить обратным ходом.