Сумировать числа до заданного предела

[kopc]

Приветствую. Я понимаю, что вопрос не по тематике зенки немного, но может кто сталкивался с подобной задачей.

Суть в следующем. В бд храниться список из цен. Из бд забираются цены и еще 1 столбец. В формате текст:цена

Цены
3.30
3.30
0.93
0.85
0.84
0.71

Задается число, например 7,5.

Задача. Сложить цены таким образом чтобы получилось число максимально приближеное к 7,5. Точнее либо больше 7,5, либо равно ему.

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

 

[[Pacman]]

Опишите пример более подробней с математической точки зрения. То есть напишите как должно выглядеть от и до для 5-6 строк. Что с чем суммироваться.
Пока: Есть список цен. Есть условие размытое (так все таки макс приближенное или больше или равно 7,5?) напишите четко. от 6 до 8 в 1 варианте, и 7,5 и 999 во втором, есть разница, напишите четкое условие. Откуда берутся данные для суммирования тоже не понятно. Просто ячейки из вашего примера 1 и 2? А если не наберется больше 7,5 то и третье число? В общем задайте четкие условия, иначе не возможно вам помочь.

Пока логика видна таким образом.
После всех манипуляций со сложением
Делаете проверку из кубика if больше или равно проверочная переменная(7,5) переменной summa
Из кубика if есть 2 выхода, красный и зеленый.
Зеленый:Если больше то делаем то что вам нужно, пишется куда то. Далле то же самое но с другими ячейками.
Красный: Если меньше то складывается еще с одним числом которое выше по ячейки на 1. И опять эта же проверка.

И конечно вставить счетчик на сколько чисел действий вообще производить, на то что бы брались другие ячейки и куча других нюансов, но кусок с проверкой примерно такой.

Если помогло то описывать пример не нужно.

 

[doc]

Опишите пример более подробней с математической точки зрения. То есть напишите как должно выглядеть от и до для 5-6 строк. Что с чем суммироваться.
Пока: Есть список цен. Есть условие размытое (так все таки макс приближенное или больше или равно 7,5?) напишите четко. от 6 до 8 в 1 варианте, и 7,5 и 999 во втором, есть разница, напишите четкое условие. Откуда берутся данные для суммирования тоже не понятно. Просто ячейки из вашего примера 1 и 2? А если не наберется больше 7,5 то и третье число? В общем задайте четкие условия, иначе не возможно вам помочь.

Пока логика видна таким образом.
После всех манипуляций со сложением
Делаете проверку из кубика if больше или равно проверочная переменная(7,5) переменной summa
Из кубика if есть 2 выхода, красный и зеленый.
Зеленый:Если больше то делаем то что вам нужно, пишется куда то. Далле то же самое но с другими ячейками.
Красный: Если меньше то складывается еще с одним числом которое выше по ячейки на 1. И опять эта же проверка.

И конечно вставить счетчик на сколько чисел действий вообще производить, на то что бы брались другие ячейки и куча других нюансов, но кусок с проверкой примерно такой.

Если помогло то описывать пример не нужно.

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

 

[arhip1985]

прикольная задачка. думаю где такое может пригодится - придумал один вариант) например у клиента есть бонус на 7,5 рублей и система ему сама должна предоставить варианты, которые максимально вмещают разнообразие товаров.. но наверно это не этот вариант.. условие задачи у меня не сложило однозначного понимания как у дока, есть вопрос - можно ли например несколько цен одного и того же товара складывать и тд

 

[kopc]

Я и правда не точно описал задачу. Прошу прощения.

По факту задача действительно похожа на то что описал arhip1985

Условия. Одну строку можно использовать только 1 раз. Число должно быть больше либо равно заданному. Желательно, чтобы превышение было минимальным.

На данный момент реализована задача следующим образом.
Получаю из базы данных все строки, где цена ниже заданного числа, выстраиваю по убыванию.
Потом беру первую строку строку с удалением, дроблю ее на 2 переменные. фигню и цену. Цену добавляю к 0, сморю не превысило ли получившиеся число заданное, если не превысило, то складирую содержимое фигни в список.
Потом опять беру строку с удаление, прибавляю цену к получившемуся в прошлом шаге число, если меньше заданного, то записываю в список и повторяю.
Когда результат всего этого превышает заданное число, то я его "запоминаю", потом вычитаю последнее использованное число из суммы.

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

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

Потом сравниваю число из 1й и 2й запомненной переменной. Где число получилось меньше, тот вариант и использую.

Мне просто кажется эта последовательность действий не самой оптимальной. Может есть какие-то другие пути решения задачи?

 

[S16er1um]

Интересная задача. Смотрю в сторону остатка от деления. Ещё не знаю как, но пока помозгую, а вы тоже подумайте. Мне кажется это верный вариант

 

[doc]

Интересная задача. Смотрю в сторону остатка от деления. Ещё не знаю как, но пока помозгую, а вы тоже подумайте. Мне кажется это верный вариант

о чём речь?

 

[S16er1um]

о чём речь?

про это

но ещё не знаю что с ним делать и как) ещё всё очень сыро

 

[capturis]

На этом этапе тебе название товара не нужно. Считай матрицу цен.
Складываешь цены все со всеми, выбираешь то, которое ближе к нужному. ХЗ может кто на C# тебе сниппет накидает.
Допустим надо 7.5
цены
1,2,3,4,5
тогда ближайшие результаты 4+4 и 3+5, без повторов только 3+5.
[TABLE="class: brtb_item_table"][TBODY][TR][TD]1[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]4[/TD]
[TD]5[/TD][/TR]
[TR][TD]2[/TD]
[TD]4[/TD]
[TD]5[/TD]
[TD]6[/TD]
[TD]7[/TD][/TR]
[TR][TD]3[/TD]
[TD]5[/TD]
[TD]6[/TD]
[TD]7[/TD]
[TD]8[/TD][/TR]
[TR][TD]4[/TD]
[TD]6[/TD]
[TD]7[/TD]
[TD]8[/TD]
[TD]9[/TD][/TR]
[TR][TD]5[/TD]
[TD]7[/TD]
[TD]8[/TD]
[TD]9[/TD]
[TD]10[/TD][/TR][/TBODY][/TABLE]

 

[S16er1um]

На этом этапе тебе название товара не нужно. Считай матрицу цен.
Складываешь цены все со всеми, выбираешь то, которое ближе к нужному. ХЗ может кто на C# тебе сниппет накидает.
Допустим надо 7.5
цены
1,2,3,4,5
тогда ближайшие результаты 4+4 и 3+5, без повторов только 3+5.
[TABLE="class: brtb_item_table"][TBODY][TR][TD]1[/TD][TD]2[/TD][TD]3[/TD][TD]4[/TD][TD]5[/TD][/TR]
[TR][TD]2[/TD][TD]4[/TD][TD]5[/TD][TD]6[/TD][TD]7[/TD][/TR]
[TR][TD]3[/TD][TD]5[/TD][TD]6[/TD][TD]7[/TD][TD]8[/TD][/TR]
[TR][TD]4[/TD][TD]6[/TD][TD]7[/TD][TD]8[/TD][TD]9[/TD][/TR]
[TR][TD]5[/TD][TD]7[/TD][TD]8[/TD][TD]9[/TD][TD]10[/TD][/TR][/TBODY][/TABLE]

не канает. ваш вариант оптимален лишь при условии, что число должно быть суммой двух известных чисел. на практике же сумма 3х мелких может быть ближе чем сумма 2 больших.
как вариант
1.7+0.5+0.4 ближе к 2.5, чем 1 + 2.

 

[capturis]

не канает. ваш вариант оптимален лишь при условии, что число должно быть суммой двух известных чисел. на практике же сумма 3х мелких может быть ближе чем сумма 2 больших.
как вариант
1.7+0.5+0.4 ближе к 2.5, чем 1 + 2.

ТС разберется, сколько ему чисел складывать. Суть в том, чтобы список не переписывать по сто раз.

 

[Ande]

А что если рассмотреть это как задачу про рюкзак? И решить сторонней библиотекой (это одна из первых ссылок в поиске, работоспособность не проверял)?
То есть вам надо решить такую задачу:
F(x) = P1 * X1 + P2 * X2 +...+Pn *Xn ->min
P1 * X1 + P2 * X2 +...+Pn *Xn>=7,5
X1 - используется ли 1 товар при составлении суммы
P1 - цена 1-го товара