별 5 개 등급 시스템에는 알려진 등급 수 N (투표)이 있습니다.
또한 모든 N 등급의 최종 (가중) 평균을 가지고 있습니다 . R (소수점 2 자리까지 부동)이라고 가정 해 보겠습니다.
가능한 모든 조합 (가중 평균 합계)을 생성하고 R을 발생시키는 하나만 인쇄하는 가장 좋은 방법 (알고리즘)을 알고 싶습니다. 가능한 "모든"조합을 인쇄하는 것은 제가 찾고있는 것이 아닙니다. 왜냐하면 그것은 큰 N과 작은 R에 대해 수백억에서 실행될 것이기 때문입니다. 저는 파이썬 초보자가되는 것에서 한 걸음 벗어 났지만 그것은 선택의 언어가 될 것입니다. 그리고 바로이 연습이 언어에 대한 저의 소개입니다. 이 문제에 대한 최선의 접근 방법은 무엇입니까? 접근 방식은 내 질문이지만 코드에 대한 힌트는 대단히 감사합니다.
예:
N = 20 명의 고객이 제품을 평가했습니다.
R = 3.85는 평균 평가입니다.
출력 : [14, 0, 0, 1, 5]는 146 개 중 하나의 가능한 조합입니다. "14 개의 별 5 개, 4 개의 별 0 개, 3 개의 별 0 개, 2 개의 별 1 개, 1 개의 별 5 개"
그리고 조합 : [487, 0, 1, 0, 12]는 N = 500 및 R = 4.90 등에 대해 1154 중에서 하나의 가능한 조합입니다.
총 별 수는 N * R입니다 (예 : 20 * 3.85 = 77). 이제 총 코인 수가 고정되어 있다는 점을 제외 하면 변경 문제 와 비슷한 것이 있습니다 .
효율적인 솔루션은 총액을 초과하지 않는 많은 큰 코인 (별 5 개 등급)으로 시작하여 총액을 차지하지 않는 등급을 얻을 때까지 감소하는 것입니다. 여전히 작동하지 않는 솔루션을 확인하게되지만 특히 큰 문제 크기의 경우 모든 솔루션을 확인하는 것보다 훨씬 빠릅니다.
여기 내 솔루션이 있습니다. (편집 : 솔루션 디버그 됨. 최적의 솔루션이라고 생각하지 않지만 무차별 대입보다 낫습니다. N = 20 R = 3.85의 샘플 케이스에 대한 1931 개의 재귀 호출)
def distribution(total, maxRating, N, solution):
if total == 0 and N == 0:
return [solution + [0] * maxRating] #we found a solution
if total == 0 or N == 0:
return [] # no solution possible
largestUpperLimit = min(total // maxRating, N) # an upper limit for the number of reviews with the largest rating
largestLowerLimit = max((total - N * (maxRating -1)) // maxRating, 0) # a lower limit for the number of reviews with the largest rating
if N < largestLowerLimit:
return [] # there aren't enough ratings to make any solutions
else:
solutions = []
for i in range(largestLowerLimit, largestUpperLimit + 1): # plus 1 to include the upper limit
solutions.extend(distribution(total - i * maxRating, maxRating - 1, N - i, solution + [i]))
return solutions
# Using the function example:
solutions = distribution(N * R, 5, N, [])
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다