MySQL 찾기 하위 토탈

StackOverflow https://stackoverflow.com/questions/397384

문제

편집하다:

나는 너희들을 읽게한다는 것은 내가 관심을 덜 받는다는 것을 의미한다. 내 사과. 더 간단한 버전은 다음과 같습니다.

Bill은 매장에서 $ 100 달러 상당의 품목을 받았습니다.

그는 정확히 30 달러를 돌려 받기에 충분한 품목을 반환하고 싶어합니다.

상점에는이 작업을 수행하는 데 도움이되는 반환 시스템이 있습니다.

그가 항목을 스캔 한 후 데이터는 다음과 같습니다.

       item ¦   price ¦

socks             4.00
cheap tv         22.00
book on tape      9.00
book on paper     7.00
party hats        3.00
picture frame    10.00
hammer            5.00
juicer           16.00
mysql guide      24.00

total items  ¦ total price ¦
            9   100.00

Option 1
===============
item ¦          price ¦
cheap tv        22.00
party hats       3.00
hammer           5.00
===============

Option 2
===============
item ¦          price ¦

socks            4.00
picture frame   10.00
juicer          16.00
===============

Option 3
===============
item ¦          price ¦

book on tape    9.00
hammer          5.00
juicer         16.00

나는이 모든 것을 만들었 기 때문에 아마 몇 가지 옵션을 놓쳤을 것입니다.

따라서 큰 문제는 다음과 같습니다.

항목의 조합을 반환 할 수있는 하나의 쿼리가있는 방법 (아마도 그룹과 함께)이 있습니까?

감사!

ㅏ

도움이 되었습니까?

해결책

품목의 수가 충분히 작 으면 SQL로이를 무차별하게 만들 수 있습니다. 이것은 솔루션을 빠르게 작성하는 것이 될 수 있지만 아마도 더 똑똑한 일을하고 싶을 것입니다. "배낭 문제"NP 완료입니다.

항목 수가 큰 경우 동적 프로그래밍 알고리즘을 탐구해야합니다. 이것이 신청서에 얼마나 중요한지 스스로에게 물어봐야합니다.

품목의 수가 비교적 작다면 이것을 무차별 할 수 있습니다. 일치하는 1,2 또는 3 개의 항목의 조합을 찾는 Brute-Force SQL 문 (요청한 것)은 다음과 같습니다. 이것이 만족스럽지 않은 경우, 아마도 SQL 이이 작업에 적합한 도구가 아닐 수도 있습니다.

SELECT
   i1.id AS id1,
   NULL AS id2,
   NULL AS id3,
   i1.amount
FROM
   items i1
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount AS total
FROM
   items i1,
   items i2
WHERE
   i1.amount + i2.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount + i3.amount AS total
FROM
   items i1,
   items i2,
   items i3
WHERE
   i1.amount + i2.amount + i3.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id AND
   i2.id <> i3.id

Oracle에서는 Cube 기능을 사용하여 MySQL 동등성에 대해서는 확실하지 않습니다.

다른 팁

정확히 $ 30까지 요약 한 모든 서브 세트를 요구합니다.

이것은 비슷하게 들립니다 서브 세트 합계 문제, 그리고 배낭 문제, 그래서 나는 당신이 간단한 쿼리로 이것을 할 수 있다는 것을 강력히 의심합니다. 당신은 아마도 t-sql로 돌아 가야 할 것입니다. 그러나 심지어 그것은 아마도 못 생겼을 것입니다.

프로그래밍이 여기로가는 길이라고 생각합니다.

나는 그룹이 할 수 있다고 생각하지 않습니다.

선택한 프로그래밍 언어 또는 저장된 절차에서 모든 순열을 찾거나 시도하는 것보다 더 나은 방법을 생각할 수 없습니다.

30 달러가 넘는 품목이 있다면 생략 할 수 있습니다.

일부 기준으로 "최고의"옵션을 원한다면 약간의 개선이있을 것입니다.

이 문제는 실제로 P/NP입니다. 예를 들어, 당신은 아마도 Brute Force Search없이 가장 적합한 기사 가격을 찾을 수 없으며, 고객 매장이 크면 검색이 매우 오래 지속될 수 있습니다.

기존 알고리즘 중 일부를 사용할 수있는 일부 알고리즘을 사용할 수 있지만 SQL이 아닌 알고리즘이 모두 비 SQL이라는 것을 두려워합니다.

나는 당신의 문제를 근사화하는 것을 제안합니다.

Wanted Price에 가장 적합한 하나의 기사를 찾는 절차/쿼리를 작성하고 새로운 변경 사항을 위해 다시 전화하는 것보다. 완벽하지는 않지만 일을 할 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top