MySQL의 PHP 서브셋 합계 문제

Question

다음 문제 :

나는 노래가있는 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까지 추가하는 기간을 돌려 주었다. 그래서 내 문제는이 문제를 어떻게 해결할 것인가? 원하는 시간까지 합치는 노래 또는 해당 노래 이름으로 목록을 인쇄하십시오.

This은 내가 찾은 최고의 답변 중 하나 인 것 같지만 데이터베이스에 적용 할 수 없습니다.

Answer 1

설명하는 내용은 Knapsack Problem입니다. 대학에 다닐 때 Dynamic Programming을 사용하여 이와 같은 문제를 공격했습니다. ! 트랙에 대한 당신의 시간이 경우 매우을 통해 반복하고 계산하는 긴

- 하나 (또는 ​​그 이상) 작동하는 복잡성 O(n!), 또는 계승 길이 문제가 될 때까지

brute-force 방법은 (단지 모든 조합을 시도 (초 나에게 가장 쉬운 수학을 보인다)을 int로 저장 한 다음 배낭의 크기는 3300-3900 (3,600초 == 1 시간)입니다.

항상 일치하는 첫 집합을 반환하는 목표이다, 항상 ra를 반환하려면 ndom 세트?

_{^{주 - 자루 크기를 경계하여 가능한 답 수를 크게 늘립니다.}}