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

Есть задача набрать на не меньшую сумму элементов с определенной ценой, а если это не возможно то на меньшую Пример: надо набрать 10 000 есть 20 000 Так вот алгорим должен взять 8 000+3 000 Господа, кто может поделитесь алгоритмом.

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

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

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

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

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

Посмотри тут /  Может чего найдется.

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

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

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

Да фиг ты так подберешь, и пример у тебя странный: Пример: надо набрать 10 000 есть 20 000 Так вот алгорим должен взять 8 000+3 000 > 10 000 А почему алгоритм не должен взять хотя бы 8000 + 2 * 1 000 = 10 000 ? При наличии 2 шт. по 1 000.

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

читай 3

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

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

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

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

рекрусия...

любой не сложный

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

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

не знаешь?

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

терпит до 20.10.05

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

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

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

неа

бывает...

Вот навоял вроде работает. Осталось=СуммаДоговора-СуммаВсего; ТаблицаСтоимости.ВыбратьСтроки; Не оптимально, зато есть решение (хотя его надо еще проверит)

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

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

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

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

точно

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

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

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

А подумать?

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

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

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

(+36) Блин неверно... Сумма 10 000 по этому алгоритму будет списана как 15 000, а минимум - 11 000.

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

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

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

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

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

ты думаешь я удивлен... что ты не осилил... ни капельке... поверь... off: Волшебнику... а что это за косяк с ["cb">]

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

КонецПроцедуры Это для задачи "набрать максимальную сумму не большую данной" Без оптимизации по скорости, но с частичной оптимизацией по количеству итераций. По количеству итераций: 1. нет расчета начального значения для цикла. Оно должно быть равным не Кол, а мин(кол,цел(сумма/цена)) 2. нет группировки строк с одинаковой ценой 3. нет возврата при невозможности добрать нужную (уже найденную) сумму остальными товарами Для оптимизации по быстродействию - переделать ТЗ на массивы. Убрать рекурсивный вызов. (сделать стек на массиве) Убрать умножение (а*цена)

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

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

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

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

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

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

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

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

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

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

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

правильно ;)

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

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

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

Условие в !!! см.

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

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

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

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

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

не просто перебераем:

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

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

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

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

Да. Причем есно -если сумм только по одной, то он значительно проще.  КонецЕсли; Тестовый вариант  - значения 100000,10000,1000,100,10,1 набрать 100101... есно наберет.

// и ТЗ конечно можно не передавать, и из всех вызовов убрать...

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

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