특수 할당 문제에 대한 효율적인 솔루션

Question

주어진 경우 :

-A 주어진 컨테이너 유형에 배치되는 데 필요한 비용 집합입니다.

- 사용 가능한 컨테이너가 각각있는 컨테이너 유형 세트.

예 :

양 * 컨테이너 타입 : 5 * A, 3 *의 B, 2 * C

가방 (비용)

3 * X (A = 2, B = 3, C = 1)

2 * Y (A = 5, B = 2, C = 2)

1 * Z (A = 3, B = 3, C = 1)

문제 :

비용을 최소화 할 수 있도록 컨테이너에 항목을 배치하는 것이 가장 좋습니다. 단순화를 위해 단일 유형의 컨테이너에만 항목을 배치하십시오.

문제를 해결하기 위해 헝가리 방식을 시도했지만 O (n³)의 런타임에서는 큰 문제 (예 : 10 만 개 항목)에 대해서는 매우 금지되어 있습니다.

현재의 솔루션은 항목 - 컨테이너 조합을 비용 (오름차순)으로 주문하고 O (n log n)에 충분한 양의 첫 번째 컨테이너를 할당하는 욕심 많은 접근 방식입니다.

더 좋은 솔루션이 있습니까?

Answer 1

유전체가 생성, 변이 및 교차 번식하기 쉽습니다. 최적의 비 조합 솔루션이있을 수 있습니다. 나는 당신의 문제를 잘 이해하면

Answer 2

, 당신은 단지 약간의 수학이 필요합니다

http://en.wikipedia.org/wiki/Optimization_%28mathematics%29

Answer 3

이 문제는 Knapsack problem의 변종이다, 위키피디아 페이지에서 시작하고 거기에서 읽어 보시기 바랍니다.

그리 디 알고리즘은 합리적으로 좋은 appoximation 것으로 알려져 있으므로 충분히 좋습니다.

Answer 4

assignment problem을 linear program으로 작성하고 simplex algorithm을 사용하여 해결 했습니까?