0
내가 읽는 교과서에서 아래의 문제를 해결하고 싶지만 어떻게해야하는지 잘 모르겠습니다. 우리가 세트의 최대 빈도가 아니라 세트의 최대 빈도가 필요하다고 생각하기 때문에 사실 그것이 확실한 지 아닌지는 사실입니다. 생각할 수있는 가치가 없습니다.히팅 세트 알고리즘 근사치
집합 A = {a 1 ..... a n} 및 집합 B, 예를 들어 B 1, B 2, ..., B m. 각 요소 ai ∈ A는 가중치 wi> 0을 가진다. 문제는 H의 요소의 총 가중치가 최소화되도록 부분 집합 H ⊆ A를 찾고, 동일한 시간에 에 H가 즉, H ∩ B i는 모든 i = 1, ..., m에 대해 ∅이 아니다. b = max i | B i | 서브 세트 B 1, B 2, ..., B m의 최대 크기이다. 이 문제에 대해 다항식 시간 b- 근사 알고리즘을 제공하십시오.
'b * m'은 모든 세트의 모든 멤버십을 반복하는 데 걸리는 시간입니다. 예를 들어, 세트의 요소 빈도를 계산하는 것과 같습니다. 그 질문은 나에게 불분명하다. "b 근사 알고리즘"에 대한 정의는 무엇입니까? 그들이 다항식을 말할 때, m 또는 b의 다항식을 의미합니까? – btilly