사전에서 최적의 그룹 선택 Python

Question

그래서 key : value (tuple)가있는 사전이 있습니다. 이 같은. { "name":(4,5), ....} 여기서 (4,5)는 두 개의 카테고리 (cat1, cat2)를 나타냅니다. 두 번째 범주의 최대 개수를 감안할 때 첫 번째 범주가 최대화되거나 최소화되도록 사전 항목의 최적 조합을 찾고 싶습니다.

예를 들어, maxCat2 = 15 인 경우, 각 항목의 cat2 값을 함께 추가 할 때 사전에서 항목 조합을 찾고 싶습니다. 15 세 미만입니다. 많은 조건이있을 수 있습니다. 이러한 가능성 중에서도 각 항목에 대해 cat1 값을 추가 할 때 다른 항목보다 더 큰 항목을 선택하고 싶습니다.

사전에 항목의 모든 순열을 얻은 다음 각 항목이 maxCat2 기준을 충족시키는 지 확인한 다음 가장 큰 총 cat1 값을 제공하는 알고리즘을 확인하는 알고리즘을 작성했습니다. 20 개의 항목이 있다면 20 개를 확인합니다. 콤비네이션은 매우 큰 숫자입니다. 이 문제를 피하기 위해 제가 할 수있는 일이 있습니까? 감사.

Answer 1

Jochen Ritzel은 knapsack problem의 인스턴스로 볼 수 있습니다.

일반적으로 "무게"(예제에서는 "두 번째 범주")와 "값"(최소화 문제 인 경우 "비용")이 모두있는 개체 집합이 있습니다.

문제는 가중치의 합계가 지정된 최대 값을 초과 할 수 없도록 제약 조건에 따라 "값"의 합이 최대화/최소화되도록 객체의 하위 집합을 선택하는 데 있습니다.

일반적으로 문제는 다루기 어렵지만, 가중치의 합에 대한 최대 값에 대한 제약 조건이 고정되어있는 경우 dynamic programming 또는 memoization을 사용하는 다항식 시간 솔루션이 있습니다.

매우 광범위 아이디어에만 제 I 목적을 고려하여 ("값"으로) 달성 가능한 최대 합을 나타낸다

C IJ 값들을 정의 할 곳 총중량 (선택한 하위 집합의)는 j을 초과 할 수 없습니다.

는 IJ C _{을 계산하기 위해 여기에 두 가지 선택이 있습니다.난}이 서브 세트에 포함

• 어느 요소 다음

  C _IJ = 값 _I + C _{I-1, J-중량 i}

  ,

• 또는 요소 I는 = IJ

  그래서, 선택된 객체의 부분 집합 C _{I-1, J}

C 아니다

둘 중 최대 값은 파이가되어야합니다. cked.

N는 요소 수와w 경우 그 대답은 C NW에서 끝나는, 최대 총 중량이다.