재배포 알고리즘

Question

크기가 다른 천개의 버킷이 있습니다. 각 버킷은 다른 무게의 빨간색과 파란색 공으로 구성됩니다. 총 공 중량의 60 %가 빨간 공에서 나오고 40 %가 파란색 공에서 나옵니다. 각 버킷에는 무작위 수의 볼, 빨간색과 파란색 볼의 무작위 배분 및 공 중량의 임의 분포가 있습니다.

각 물통이 빨간 공에서 59-61 %의 공 중량과 푸른 공에서 39-41 %의 공 중량으로 구성되도록 공의 재배포를 수행해야합니다. 각 버킷은 재배포 이전과 정확히 동일한 가중치를 가져야하지만 각 버킷의 볼 수는 이전 수와 일치하지 않아도됩니다. 공을 나눌 수도 있지만 각 스플릿에는 비용이 있습니다.

누구나 알고리즘 방향으로 나를 가리킬 수 있습니까?

감사합니다.

Answer 1

한 가지 가능한 방법은 다음과 같은 방법으로 혼합 정수 프로그래밍 문제를 공식화하는 것입니다. 확실하지는 않습니다. 다른 훨씬 더 효율적인 솔루션이있을 수 있습니다.

각각 R 1, r 2, ... r R 및 b 1, b 2, ... b B의 무게를 가진 R 빨간색 볼과 B 파란색 볼이 있다고 가정 해보십시오.

Say Rij는 버킷 j에 할당 된 빨간 공 i의 비율입니다. RBINij는 Rij> 0이면 1이고 그렇지 않으면 0 인 2 진수입니다. 가능한 한 많은 Rij의 0 (그리고 RBINij의 0)을 가능한 한 많이 만들고 싶습니다.

마찬가지로 Bij는 버킷 j에 할당 된 파란 공 i의 비율입니다. BBINij는 Bij> 0 인 경우 1이고 그렇지 않은 경우 0 인 2 진수입니다. 가능한 한 많은 수의 Bij의 0 (및 BBINij의 0)을 가능한 한 많이 만들고 싶습니다.

Constraints: 
summation over i(wi*Rij) <= 1.564*summation over i(wi*Bij) (61-39 ratio) { for all j buckets } 
summation over i(wi*Rij) >= 1.439*summation over i(wi*Bij) (59-41 ratio) { for all j buckets } 
RBINij >= Rij 
BBINij >= Bij 
+ maybe more constraints like the total weight etc. 

Objective Function: 
Minimize(Ci*summation over i(RBINij + BBINij))