정수 배열을 가지고 있기 때문에 각 그룹의 합계가 최소 인 알 수없는 그룹에서 정렬해야합니다.합계가 가장 작은 그룹으로 배열을 분할하는 방법은 무엇입니까?
예 :
Array: 2, 1, 4, 7, 1, 2, 6, 8
Number of groups = 3
Result:
Group 1 – 8, 2 = 10
Group 2 – 7, 2, 1 = 10
Group 3 – 6, 4, 1 = 11
이 어떤 alghoritham도이 문제를 해결할 수 있습니까? 나는 막혔다.
첫 번째로, 그룹의 수가 2이면이 문제는 부분 집합 합계 문제로 파티션 문제를 줄입니다. 이것은 문제가 NP 하드임을 증명하므로 효율적인 알고리즘을 찾지 마십시오.
지수가 적어도 될 경우 모든 순열을 생성하고 최상의 결과를 얻을 수 있습니다. 나는 어떤 사람들은 재귀를 싫어하는 알고 있지만, 정말 그룹의 가능성을 열거 여기를 유용
recfunc(array, groups):
if array is empty
return an array containing the element groups
else
groupsList = empty array
foreach aGroup in groups
element = array[0]
groupsList += recfun(array - element, groups where aGroup adds element)
return groupsList
이 알고리즘은 모든 가능성의 목록을 작성합니다. 그것은 상당히 비효율적이지만 구현하기에 너무 어렵지 않아야합니다. 여기에서 목록을 살펴보고 그룹의 합이 목록의 최소값인지 계산합니다.