как найти сумму (поле) в условии, т.е. "выбрать * из таблицы, где сумма (поле) <150"

Question

Мне нужно получить только определенные записи, у которых сумма значений поля размера <= 150. У меня есть таблица, как показано ниже ... </p>

userid size
1       70
2      100   
3       50
4       25
5      120
6       90

Вывод должен быть ...

userid size
1       70
3       50
4       25

Например, если мы добавим 70,50,25, мы получим 145, что составляет <= 150. </p>

Как мне написать запрос для достижения этой цели?

Answer 1

Вот запрос, который даст вышеуказанные результаты:

SELECT * FROM `users` u
WHERE (select sum(size) from `users` where size <= u.size order by size) < 150
ORDER BY userid

Однако проблема, которую вы описываете при выборе пользователей, которые наиболее точно соответствуют данному размеру, - это проблема упаковки бина . Это проблема NP-Hard , которая не может быть легко решена с помощью ANSI SQL. Однако приведенное выше, похоже, возвращает правильный результат, но на самом деле оно просто начинается с самого маленького элемента и продолжает добавлять элементы до тех пор, пока корзина не заполнится.

Общий, более эффективный алгоритм упаковки мусорного ведра состоит в том, чтобы начинать с самого большого элемента и продолжать добавлять меньшие по мере необходимости. Этот алгоритм будет выбирать пользователей 5 и 4.

Answer 2

Что вам нужно, так это жадный алгоритм . Вы не можете сделать это с помощью одного оператора SQL.

Answer 3

Но вы хотите максимизировать количество результатов или минимизировать, или вам просто все равно? Первые два случая - это оптимизация ограничений, для которой должно быть решение с использованием SQL, последний (как упоминалось выше) требует жадной стратегии.

Answer 4

Согласно вашему определению, вы можете получить любую из следующих таблиц:

userid size    userid size
1       70     2      100   

userid size    userid size
3       50     4       25

userid size    userid size
5      120     6       90

userid size    userid size
1       70     2      100   
3       50     3       50

userid size    userid size
1       70     2      100   
4       25     4       25

userid size    userid size
1       70     4       25
3       50     6       90
4       25

userid size    userid size
4       25     3       50
5      120     6       90

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

Answer 5

Это похоже на проблему суммы подмножеств . Вы определенно будете в экспоненциальном времени ...

Есть несколько способов решить подмножество сумма во времени экспоненциальная в N. Наиболее Наивный алгоритм будет цикл через все подмножества N чисел и, для каждого из них проверьте, Подмножество сумм к правильному номеру. время работы порядка O (2 ^ N * N), так как Есть 2N подмножеств и, чтобы проверить каждое подмножество, мы должны суммировать не более N элементы.

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