Проблема суммы подмножеств в PHP с MySQL - PullRequest
Новая
       43

Проблема суммы подмножеств в PHP с MySQL

2 голосов
/ 14 сентября 2011

следующее Проблема:

У меня есть база данных MySQL с песнями в ней.База данных имеет следующую структуру: 

id INT(11)(PRIMARY)
title VARCHAR(255)
album VARCHAR(255)
track INT(11)
duration INT(11)

Пользователь должен иметь возможность вводить определенное время в форму php, а функция php должна предоставить ему список всех возможных комбинаций песен, которые составляютзаданное время ± X мин.

Таким образом, если пользователь хочет слушать 1 час музыки ± 5 минут, он вводит в форму 60 минут и 5 минут порогового значения и получает все возможные наборы песен, которые суммируются.в общей сложности от 55 до 65 минут.Он не должен распечатывать дубликаты.

Я уже нашел несколько подходов к этой проблеме, но они вернули мне только продолжительность, которая складывается в X, а не названия песен и т. Д. Поэтому моя проблема заключается в том, как решить эту проблему.так что он возвращает мне идентификаторы песен, которые складываются в нужное время, или распечатывает список с соответствующими названиями песен.

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

1 Ответ

0 голосов
/ 14 сентября 2011

То, что вы описываете, является Рюкзаком Проблема . Когда я учился в колледже, мы использовали Динамическое программирование , чтобы атаковать подобные проблемы.

Методы brute force (попробуйте каждую комбинацию, пока одно (или более) произведение не станет сложностью O(n!), или проблема факторной длины - чрезвычайно длительность для перебора и посчитай!

Если ваше время для треков хранится как int (в секундах мне кажется, что это самая простая математика), то ваш размер рюкзака составляет 3300-3900 (3600 секунд == 1 час).

Ваша цель - всегда возвращать набор первый , который соответствует, или всегда возвращать набор random ?

Примечание. Ограничивая размер мешка, вы значительно расширяете число возможных ответов.

...