Есть задача набрать на не меньшую сумму элементов с определенной ценой, а если это не возможно то на меньшую
Пример: надо набрать 10 000
есть
20 000
8 000
5 000
3 000
1 000

Так вот алгорим должен взять 8 000+3 000

Господа, кто может поделитесь алгоритмом.

два по 5000... ближе

(0) Не вижу большой разницы с распределением по фифо/лифо.

нет элемент берется один раз

(2) ЛИФО и ФИФИ здесь не причем

(1) Если так то сложнее... Это наверное уже ближе будет к задачи про "груз в рюкзаке" наверное...

(0) Посмотри тут http://algolist.manual.ru/  Может чего найдется.

(4) Смысл тот же самый (в приближении конечно).

не так значит не так приближаешь

Опа... задача на мини-макс

(8) Да фиг ты так подберешь, и пример у тебя странный:

Пример: надо набрать 10 000
есть
20 000
8 000
5 000
3 000
1 000

Так вот алгорим должен взять 8 000+3 000 > 10 000

А почему алгоритм не должен взять хотя бы

8000 + 2 * 1 000 = 10 000 ? При наличии 2 шт. по 1 000.

2 Парижская фанера, Широкий делаете вид что знаете :)

(10) читай 3

(11) Ну дак объясни толком, я не понимаю условий.

ЗЫ Почему нельзя свести все к суммам (кол-во остатка * цену), а не ценам как у тебя и пройти по фифо?

(12) Блин... Тогда удачи...

Нужен любой алгоритм кроме перебора

Похоже задача схожа с задачей про рюкзак, фанере спасибо

рекрусия...

(15) любой не сложный

(18) Любой рабочий будет переборным и сложным ...

(17) Что такое "рекрусия"?

(20)не знаешь?

(18)до завтра терпит... если да.. то жди... просто пять минут осталось... не успею...

терпит до 20.10.05

(23)ну если до завтра не скажут... ченить выкину...

(22) сенкс, интересно что ты там придумал, а то я тут уже про базис Грёбнера немного прочитал. Неохото так глубоко копать.

тебеже на одиСи надо... тогда просто через ТЗ...

(21) неа

(27)бывает...

Вот навоял вроде работает.

Осталось=СуммаДоговора-СуммаВсего;
ТаблицаСтоимости.ВыбратьСтроки();
НомерСтрокиБольшойСуммы=0;
Пока (ТаблицаСтоимости.ПолучитьСтроку() = 1) и (Осталось>0)  Цикл    
   Если (ТаблицаСтоимости.ОстаточнаяСтоимостьВал<=0)  Тогда        
       Продолжить;
   КонецЕсли;        
   
   Если (ТаблицаСтоимости.ОстаточнаяСтоимостьВал>Осталось)
       и (ТаблицаСтоимости.НомерСтроки<>ТаблицаСтоимости.КоличествоСтрок())  Тогда
       
       // Не будем трогать слишком большие суммы, если это конечно не последняя строка
       НомерСтрокиБольшойСуммы=ТаблицаСтоимости.НомерСтроки;
       Продолжить;
   КонецЕсли;
   
   ВремТаблицаПодбора.НоваяСтрока();
   ВремТаблицаПодбора.Цена = ТаблицаСтоимости.ОстаточнаяСтоимостьВал;
   
   Осталось=Осталось-ТаблицаСтоимости.ОстаточнаяСтоимостьВал;
КонецЦикла;

Если (Осталось>0) и (НомерСтрокиБольшойСуммы>0) Тогда
   ТаблицаСтоимости.ПолучитьСтрокуПоНомеру(НомерСтрокиБольшойСуммы);
   Если ТаблицаСтоимости.ОстаточнаяСтоимостьВал>(СуммаДоговора-СуммаВсего) Тогда            
       ТаблицаПодбора.НоваяСтрока();
       ТаблицаПодбора.Цена = ТаблицаСтоимости.ОстаточнаяСтоимостьВал;
   Иначе
       ТаблицаПодбора.НоваяСтрока();
       ТаблицаПодбора.Цена = ТаблицаСтоимости.ОстаточнаяСтоимостьВал;
       
       ВремТаблицаПодбора.ВыбратьСтроки();
       Пока ВремТаблицаПодбора.ПолучитьСтроку() = 1 Цикл
           ТаблицаПодбора.НоваяСтрока();
           ТаблицаПодбора.Цена = ВремТаблицаПодбора.Цена;
       КонецЦикла;
   КонецЕсли;
Иначе
   ВремТаблицаПодбора.ВыбратьСтроки();
   Пока ВремТаблицаПодбора.ПолучитьСтроку() = 1 Цикл
       ТаблицаПодбора.НоваяСтрока();
       ТаблицаПодбора.Цена = ВремТаблицаПодбора.Цена;
   КонецЦикла;
КонецЕсли;


Не оптимально, зато есть решение (хотя его надо еще проверит)

(0)Симплекс-метод тебе поможет

(28) Может все-таки "рекурсия"?

а если у нас есть
7,5,4,2 и нужно набрать 13, то алгоритм должен взять 7,4 и 2, пропустив 5. правильно?

легко, ща налабаю ...

(32) точно

(33) Писать рюкзак 12 часов - это круто...

1. Сортировка по убыванию
2. Брать самый верхний элемент, если он меньше оставшейся суммы.
3. Обнулить его в таблице, а оставшуюся сумму - уменьшить на это число.
4. goto 2, пока оставшаяся сумма >0

Алгоритм имхо чисто итерационный, а не рекурсивный.

(36) А подумать?

(36,37) А если есть повторяющиеся числа, то перед этим их нужно сгруппировать (перед сортировкой), и брать в цикле от максимального количества до нуля.
Писать проще на рекурсии, но быстрее работает на массиве (стеке).
И цифири лучше перенести из ТЗ в Массив - раз в шесть быстрее будет....
И условия прерывания должны быть... Очень ускоряют...
(если перебрали сумму, если на оставшихся уже не добрать до уже полученного значения и т.д.)

(38) А чё думать? В куче мест стоит и работает.
Где-то в архивах realnet-а было - для Гены писал.

(36) ну собственно в (29) я так и делаю.

(+36) Блин неверно... Сумма 10 000

11 000
1 000
1 000
1 000
1 000

по этому алгоритму будет списана как 15 000, а минимум - 11 000.

(42) смотри как я сделал в случае если сумму не набрать меньшими суммами.

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


//*******************************************
procedure Choice(vlPara, vlAnswer, Sum)
   Count = vlPara.GetListSize();
   if Count > 0 then
       maxRest = 0;
       oldDifference = Sum;
       for x = 1 to Count do
           Value = vlPara.GetValue(x);
           Difference = Sum - Value;
           if Difference > 0 then
               if oldDifference > Difference then
                   oldDifference = Difference;
                   maxRest = Value;
               endif;
           elsif Difference = 0 then
               maxRest = Value;
               break;
           endif;
       enddo;
       if maxRest = 0 then
           x = vlAnswer.GetListSize();
           if x > 0 then
               vlAnswer.RemoveValue(x);
           endif;
           x = vlPara.GetListSize();
           Value = vlPara.GetValue(x);
           vlAnswer.AddValue(Value);
       else
           x = vlPara.FindValue(maxRest);
           vlPara.RemoveValue(x);
           vlAnswer.AddValue(maxRest);
           Rest = Sum - maxRest;
           if Rest > 0 then
               Choice(vlPara, vlAnswer, Rest);
           endif;
       endif;
   endif;
endprocedure

//*******************************************
procedure Make()
   vlAnswer = createobject("valuelist");
   vlPrice = createobject("valuelist");
   vlPrice.AddValue(20000);
   vlPrice.AddValue(8000);
   vlPrice.AddValue(5000);
   vlPrice.AddValue(3000);
   vlPrice.AddValue(1000);
   vlPrice.Sort(1);
   Choice(vlPrice, vlAnswer, 10000);
   Count = vlAnswer.GetListSize();
   if Count > 0 then
       for x = 1 to Count do
           message(vlAnswer.GetValue(x));
       enddo;
   endif;
endprocedure

Make();


(44) щас проверил, в примере из (42) списывает 15 000 вместо 11 000...
Может действительно надо что-то вроде симплекс-метода (или чего-то там еще из исследования операций) юзать...

(43) Не осилил. Как его запустить-то...

(45) Еще раз - перебором нормально работает. Только писать нужно без ошибок.

(46)ты думаешь я удивлен... что ты не осилил... ни капельке... поверь...


off: Волшебнику... а что это за косяк с ["cb">]

+39 по ушустрению алгоритма... все числа которые больше суммы... можно удалить...


короче думай сам...

перем ЛучшаяДельта;
перем ТЗ;
Функция Рюкзак(ТЗ,Сумма,знач нач=0)
    Если Сумма=0 Тогда
       //ТЗ.Заполнить(ТЗ,,,"ВыбКол");  // Глючит!!!!
       ТЗ.ВыбратьСтроки();
       Пока ТЗ.ПолучитьСтроку()=1 цикл
           ТЗ.ВыбКол=ТЗ.ТемпКол;
       КонецЦикла;    
       ЛучшаяДельта=0;  
       возврат 0; // нашли точное соответствие
    ИначеЕсли Сумма<0 Тогда
       возврат 1;  // перебор
    ИначеЕсли сумма<ЛучшаяДельта Тогда    
       //ТЗ.Заполнить(ТЗ,,,"ВыбКол");  // Глючит!!!!!
       ТЗ.ВыбратьСтроки();
       Пока ТЗ.ПолучитьСтроку()=1 цикл
           ТЗ.ВыбКол=ТЗ.ТемпКол;
       КонецЦикла;    
       ЛучшаяДельта=Сумма;  // улучшили решение
    КонецЕсли;
    Если нач=ТЗ.КоличествоСтрок() Тогда
       возврат 1; // пробежали до конца
    КонецЕсли;    
    нач=нач+1;  
    а=ТЗ.ПолучитьЗначение(нач,"кол");
    Пока а>=0 цикл    
       ТЗ.УстановитьЗначение(нач,"ТемпКол",а);
       Если Рюкзак(ТЗ,Сумма-ТЗ.ПолучитьЗначение(нач,"цена")*а,нач)=0 Тогда
           возврат 0;  
       КонецЕсли;    
       а=а-1;
    КонецЦикла;    
    возврат 1;
КонецФункции    
Процедура Сформировать()
    ТемпТЗ=СоздатьОбъект("ТаблицаЗначений");
    ТЗ=Создатьобъект("ТаблицаЗначений");
    ТЗ.НоваяКолонка("ТемпКол","Число",10,0);// Первая!!!
    ТЗ.НоваяКолонка("Наим");
    ТЗ.НоваяКолонка("Кол","Число",10,0);
    ТЗ.НоваяКолонка("Цена","Число","12",2);
    ТЗ.НоваяКолонка("ВыбКол","Число",10,0);
    ТЗ.НоваяСтрока();
    ТЗ.Наим="3 коп.";
    ТЗ.Кол=5;
    ТЗ.Цена=0.03;
    ТЗ.НоваяСтрока();
    ТЗ.Наим="5 коп.";
    ТЗ.Кол=5;
    ТЗ.Цена=0.05;
    ТЗ.НоваяСтрока();
    ТЗ.Наим="10 коп.";
    ТЗ.Кол=5;
    ТЗ.Цена=0.10;  
    ТЗ.ВыбратьСтроку();
    Сумма=0.34;
    ЛучшаяСумма=0;    
    ЛучшаяДельта=Сумма;            
    ТЗ.Сортировать("-Цена");
    ТЗ.Заполнить(0,,,"ВыбКол,ТемпКол");
    Сообщить("Набираем сумму "+Сумма);
    Рюкзак(ТЗ,Сумма);
    ТЗ.Заполнить(0,,,"ТемпКол");
    ТЗ.ВыбратьСтроку();
КонецПроцедуры
Это для задачи "набрать максимальную сумму не большую данной"
Без оптимизации по скорости, но с частичной оптимизацией по количеству итераций.
По количеству итераций:
1. нет расчета начального значения для цикла.
Оно должно быть равным не Кол, а мин(кол,цел(сумма/цена))
2. нет группировки строк с одинаковой ценой
3. нет возврата при невозможности добрать нужную (уже найденную) сумму остальными товарами
Для оптимизации по быстродействию - переделать ТЗ на массивы.
Убрать рекурсивный вызов. (сделать стек на массиве)
Убрать умножение (а*цена)

Вариант "тупого" перебора:

//*******************************************
Процедура Сформировать()
   Перем Массив[5];
   
   Массив[1] = 20000;
   Массив[2] = 8000;
   Массив[3] = 5000;
   Массив[4] = 3000;
   Массив[5] = 1000;
   
   п_НаилучшаяДельта            = 0;
   п_ИскомоеЧисло                = 10000;
   п_ИскомаяПоследовательность = "";

   Сч = 0;
   Для Сч = 1 По 5 Цикл
       п_НаилучшаяДельта        = п_НаилучшаяДельта - Массив[Сч];
   КонецЦикла;
   
   ВремяНач = _GetPerformanceCounter();
   Сч = 0;
   Для Сч = -32 По -1 Цикл // 32 = 2^5
       п_Код = "";
       п_Число = -Сч - 1;
       Пока п_Число > 1 Цикл
           п_Остаток = п_Число%2;
           п_Код     = Строка(п_Остаток) + п_Код;
           п_Число   = Цел(п_Число/2);
       КонецЦикла;
       п_Код = Прав(Формат("", "С5") + (Строка(п_Число) + п_Код), 5);
       
       п_Дельта    = п_ИскомоеЧисло;
       п_ДлинаКода = СтрДлина(п_Код);
       
       СчСимв = 0;
       Для СчСимв = 1 По п_ДлинаКода Цикл
           п_Символ = Сред(п_Код, СчСимв, 1);
           п_Дельта = п_Дельта - ?(п_Символ = "1", Массив[СчСимв], 0);
       КонецЦикла;
       
       Если п_Дельта = 0 Тогда // Нашли
           п_ИскомаяПоследовательность = п_Код;
           Прервать;
       ИначеЕсли п_Дельта < 0 Тогда
           Если п_Дельта > п_НаилучшаяДельта Тогда
               п_НаилучшаяДельта = п_Дельта;
               п_ИскомаяПоследовательность = п_Код;
           КонецЕсли;
       КонецЕсли;
   КонецЦикла;
   
   Сч = 0;
   Для Сч = 1 По 5 Цикл
       Если Сред(п_ИскомаяПоследовательность, Сч, 1) = "1" Тогда
           Сообщить(Массив[Сч]);
       КонецЕсли;
   КонецЦикла;
   
КонецПроцедуры

не айда... набор сумм плавающий... массив юзать здесь низя...

(52) Ничего не понял... почему нельзя массив???
Задай сразу 100000 в размерность. Да и всех делов.
Как я уже говорил - раз в шесть быстрее ТЗ...

(52) Можно через СЗ или ТЗ, это непринциально. Просто работать будет подольше.

(53) Проверял. Доходит до 9 раз...

(53)а вдруг получиться 100001 элементов надо...

(54) У тебя работает быстрее, чем (50)?
строку лучше поменять...
а=ТЗ.ПолучитьЗначение(нач,"кол");
на
а=мин(ТЗ.ПолучитьЗначение(нач,"кол"),цел(сумма/ТЗ.ПолучитьЗначение(нач,"цена")));
и соответственно убрать условие на сумма<0...
//ИначеЕсли Сумма<0 Тогда
//         возврат 1;  // перебор

(56) Тогда беда...
Но не совсем ;-))
Можно юзать #ЗагрузитьИзФайла...

(57) У тебя написано: "Это для задачи "набрать максимальную сумму не большую данной"". Я писал для (0): "Есть задача набрать на не меньшую сумму элементов с определенной ценой, а если это не возможно то на меньшую".
Вообще-то не сравнивал :-)  Просто интересно было написать.
(58) Это с изменением *.txt и переоткрытием?

(59) То есть если сумма всех элементов больше нужной суммы - берем все элементы, ежели нет, то либо берем один минимальный, либо не берем вообще?

(60) Как я понял автора (0) нужно максимально приблизиться к искомой сумме, лучше с перебором, если невозможно, то с недобором.

(61) правильно ;)

(61) Если сумма всех элементов больше необходимой суммы - то искать приближение сверху, иниче снизу?
Это одна и та-же задача. Причем условие видимо формулировалось школьником.
Чтоб найти приближение сверху - делаем
СуммаКоторуюНадоНайти=Сумма(Цена*Количество)-СуммаКоторуюНадоНайти.
Находим приблежение к новой сумме. И во всех строках меняем ВыбКол на (Кол-ВыбКол)
(не лучший способ, но ничего страшного)
А если сумма всех элементов меньше либо равна искомой сумме - то есно берем все элементы.

(63) >> Это одна и та-же задача. Причем условие видимо формулировалось школьником.

Чье условие !?

(63) Если честно, то я твой алгоритм еще не разбирал  :-) Да и с рекурсией закручено...

(64)Условие в (0)!!! см. (63)

(66) я совсем не школьник

(66) и вообще я ее решил, см выше

(67) А отчего такая странная формулировка.
В (0) Даже не написано, чего надо минимизировать.
И что значит условие "Есть задача набрать на не меньшую сумму элементов с определенной ценой, а если это не возможно то на меньшую" ???
Повторюсь дословно оно означает, что если сумма элементов меньше или равна искомой, то взять все. И что надо минимизировать? Дельту? - тогда (50+63)
Если ничего - то по условию задачи - можно ВСЕГДА брать ВСЕ элементы.

(68) Как ты её решил - просто перебираем все элементы пока не достигли искомой суммы...
(пока суммаТекущая<СуммаКоторуюНадоПолучить)...
Ну никак не тянет на 69 постов в ветке...

(69) согласен формулировка не четкая. Торопился.

(70) не просто перебераем:
   Если (ТаблицаСтоимости.ОстаточнаяСтоимостьВал>Осталось)
       и (ТаблицаСтоимости.НомерСтроки<>ТаблицаСтоимости.КоличествоСтрок())  Тогда
       
       // Не будем трогать слишком большие суммы, если это конечно не последняя строка
       НомерСтрокиБольшойСуммы=ТаблицаСтоимости.НомерСтроки;
       Продолжить;
   КонецЕсли;

(72) Бред. В (50) решается задача минимизации. Причем находит последовательно лучшие приближения - и всегда найдет наилучшее решение. (Хотя никто не мешает поставить ограничение на количество итераций)

(73) объясни почему бред?

//*******************************************
Процедура Сформировать()
   ФлагОкончания=0;
   Пока ФлагОкончания=0 Цикл
       ФлагОкончания=1;
       ИтогПоТаблице=ВыбТаблица.Итог("Сумма");
       Дельта=ИтогПоТаблице-ИсхСумма;
       Если Дельта<0 Тогда
           Возврат;
       КонецЕсли;
       ВыбТаблица.ВыбратьСтроки();
       Пока ВыбТаблица.ПолучитьСтроку() = 1 Цикл
           Если ВыбТаблица.Сумма<Дельта Тогда
               ВыбТаблица.УдалитьСтроку();
               ФлагОкончания=0;
               Прервать;
           КонецЕсли;
       КонецЦикла;
   КонецЦикла;
КонецПроцедуры
//*******************************************
Процедура Заполнить()
   ВыбТаблица.НоваяКолонка("Сумма");
   ВыбТаблица.НоваяСтрока();
   ВыбТаблица.Сумма=20000;
   ВыбТаблица.НоваяСтрока();
   ВыбТаблица.Сумма=8000;
   ВыбТаблица.НоваяСтрока();
   ВыбТаблица.Сумма=5000;
   ВыбТаблица.НоваяСтрока();
   ВыбТаблица.Сумма=3000;
   ВыбТаблица.НоваяСтрока();
   ВыбТаблица.Сумма=1000;
   ИсхСумма=11000;
КонецПроцедуры

Потому что это вариация (70)

Итак (50):
Основной цикл походу

нач=нач+1;  
а=ТЗ.ПолучитьЗначение(нач,"кол");
Пока а>=0 цикл    
 ТЗ.УстановитьЗначение(нач,"ТемпКол",а);
 Если Рюкзак(ТЗ,Сумма-ТЗ.ПолучитьЗначение(нач,"цена")*а,нач)=0 Тогда
  возврат 0;  
 КонецЕсли;    
а=а-1;
КонецЦикла;

(77) Да. Причем есно -если сумм только по одной, то он значительно проще.
 //
 ТЗ.УстановитьЗначение(нач,"ТемпКол",1);
 Если Рюкзак(ТЗ,Сумма-ТЗ.ПолучитьЗначение(нач,"цена"),нач)=0 Тогда
  возврат 0;  
 Иначе
  ТЗ.УстановитьЗначение(нач,"ТемпКол",0);
  возврат 1;
 КонецЕсли;
Тестовый вариант  - значения 100000,10000,1000,100,10,1 набрать 100101... есно наберет.

извиняюсь ;-))
//
 ТЗ.УстановитьЗначение(нач,"ТемпКол",1);
 Если Рюкзак(ТЗ,Сумма-ТЗ.ПолучитьЗначение(нач,"цена"),нач)=0 Тогда
  возврат 0;  
 Иначе
  ТЗ.УстановитьЗначение(нач,"ТемпКол",0);
  возврат  Рюкзак(ТЗ,Сумма,нач);
 КонецЕсли;
//
и ТЗ конечно можно не передавать, и из всех вызовов убрать...

я так понимаю решением будут те строки у которых в колонке ВыбКол будут не нулевые  числа?

Да, но алгоритм подбирает снизу, для подбора сверху - (63)