알고리즘 소개 (MIT Press) 책에서 한 번 읽었습니다.k 파티션 알고리즘 - 작업 부하를 균등하게 나누기
우리는 100 페이지가있는 책을 가지고 있으며 각 페이지는 페이지 번호와 동일한 가중치를 가지고 있으므로 가중치는 1,2,3,4,5입니다. 이 가중치는 다른 언어로 번역 할 때 페이지의 난이도를 나타냅니다. 우리는 K 명의 사람들에게 페이지를 다른 언어로 번역하는 작업을 할당했습니다.하지만 작업량이 거의 같아 지도록 작업 부하를 나누어야합니다.
그래서 우리가있는 경우 5 페이지 1,2,3,4,5 즉 및 K = 3 다음 K1 = 5 2 + 3, K2 = 1 + 4 = 5, K3 = 5
을 수행 Google에서 찾을 수 없기 때문에이 문제에 대한 온라인 참조가 있습니까? 또는 이 알고리즘의 이름을 알고 있습니까?
이것은 내게 적합한 내림차순 알고리즘의 인스턴스처럼 보입니다.
첫 번째 맞는 내림차순 또는 첫 번째 맞춤 감소 또는 때로는 빈 포장 알고리즘으로 알려져 있습니다. 컨테이너로 개체를 효율적으로 포장하거나 작은 조각으로 재료 조각을 절단하는 데 사용됩니다.
모듈 Algorithm::BinPack에 Perl에 대한 좋은 구현이 있습니다.
하지만이 컨텍스트에서 bin 크기는 무엇입니까? 근로자가 할 수있는 일의 양에는 제한이 없습니다. –
나는 각 항목을 가장 작은 합계로 빈에 추가 할 수 있다고 생각하지만 첫 번째 적합 감소 알고리즘은 여전히 근사 알고리즘 일 뿐이므로 항상 최적의 솔루션을 반환하지는 않습니다. –
특별 케이스 : 난 그냥이
초등학교 가우스의 이야기를 생각 나게 재미있을 수 있다고 생각... 공상 아무것도
필요 없음, 번역자는 것이다 한 번에 두 페이지 가져 오기
1+100=101
2+99=101
...
50+51=101
이렇게 번역자들간에 50 페이지를 나누었습니다. , 그들은 x 페이지와 함께 101-x 번째 페이지를 얻게됩니다.
의사 코드 :
n=100 // 100 pages
k=5 // 5 translator
for i=1 to n/2
print "Translator " ,(i mod k) +1, "gets pages", i , " and " , n-i+1
참고 : n은 홀수했다, 또는 n/2 J로 나누어되지 않은 경우, 작업이 상당히 번역자 사이에서 분할하지 않을 경우 -이 경우 완벽하게 작동 n = 100 및 k in (1,2,5,10,25,50).
오 남자. 누군가가 NP-Hard 문제를 제기 할 때마다 알고리즘 교수가 항상이 이야기를 전했습니다. –
표지에 빨간색 모바일이 포함 된 책입니까? 나는 그 책을 좋아했다. 그것이 계속 사용되고 있다는 것을 듣고 기쁘다. – Ether
@Ether : 적어도 내가 사용했던 책 표지에 적색 모바일을 보지 못했습니다. 이전 버전에있을 수 있습니다! –
http://mitpress.mit.edu/algorithms/ – Ether