조합이 주어진 세트와 일치하는지 확인하십시오.

Question

기본적으로 주어진 조합이 주어진 세트와 일치하는 경우 반환하는 솔루션을 찾고 있습니다.

예 : 어떤 컴퓨터 실과 어떤 작업장에 어떤 장비가 있는지를 저장하는 배열이 있습니다. 특정 요구 사항을 가진 주어진 수의 사용자가 컴퓨터 실에 들어갈 수 있는지 여부를 알아야합니다. 색인은 나의 예에서 직장 번호이다. 그들은 내 컴퓨터 실에 적합하지 않거나, 내가 스캐너를 필요로 두 명의 사용자가있는 경우, 그리고 난 프린터를 필요로 세 명의 사용자를 가지고 :

$aComputerRoomEquipment = array(); 
$aComputerRoomEquipment[1] = array("PC"); 
$aComputerRoomEquipment[2] = array("PC"); 
$aComputerRoomEquipment[3] = array("PC", "Scanner"); 
$aComputerRoomEquipment[4] = array("PC", "Printer"); 
$aComputerRoomEquipment[5] = array("PC", "Scanner", "Printer"); 
$aComputerRoomEquipment[6] = array("PC"); 
$aComputerRoomEquipment[7] = array("PC", "Scanner", "Printer"); 
$aComputerRoomEquipment[8] = array("PC"); 

나는 다음과 같은 질문에 대답해야합니까?

모든 속성의 단순한 합계가 작동하지 않습니다. 프린터를 필요로하는 공간에 세 명을 배치하면 스캐너가 필요한 가난한 사람에게는 작업 공간이 남지 않을 것이기 때문입니다.

나는 모든 가능한 조합을 통해 반복하는 것을 이미 생각했지만 작업장의 수가 많을수록 더 오래 걸리고 가능하면 오래 걸릴 수 있습니다.

Answer 1

처음 읽었을 때, NP 완성 문제와 같은 냄새가났습니다. 여전히 그 향기가 있습니다.

하지만 나는 Ólafur Waage의 대답을 좋아합니다.

사용자를 한 번에 하나씩 가져 가면 문제를 해결할 수 있습니다. 즉, 제 1 사용자를 단지 그들이 필요로하는 워크 스테이션에 도착하게하거나, 적합하지 않은 경우 즉, 다음 사용자는 "프린터가 필요하지만 프린터가있는 워크 스테이션에 이미 스캐너가 있습니다"라고 표시 한 다음 프린터와 스캐너가있는 워크 스테이션에 놓습니다.

만약 당신이 원하는 것이 없다면 --- 하루 종일 방을 사용하려고하는 사용자를 위해 하루 앞두고 계획을 세우고 있으며 "알고 싶습니다" - 그러면 나는 이것에 너무 많은 시간을 보내기 전에 http://en.wikipedia.org/wiki/NP-complete을 살펴볼 것을 제안합니다.

Answer 2

이후에 필요한 것을 추가하면 어떨까요? 그러면 사람 1을 방에 추가 할 때 어떻습니까? 프린터가 필요하다는 것을 알게되고, 실내의 새로운 사람들과 현재있는 사람들에게 프린터를 추가하게됩니다.

그래서 새로운 사람을 추가 할 때 사람의 필요가 아니라 현재 상태를 확인합니다.

Answer 3

당신은 일반 세트가 아닌 멀티 세트를 사용합니다. 어쨌든, 당신이주는 유일한 예 에서처럼, 방안에있는 모든 사람들이 하나의 자원을 필요로하고, 단지 두 가지 자원 만 중요하다면, 인생은 믿을 수 없을만큼 쉽습니다 : 장비 배열을 풍부하게 (스캐너 전용, 프린터 전용, 엔트리가 중요하지 않다면!), 각 자원에 대해 min (availble, requested)만큼 많은 하나의 자원을 할당하고 (해당 요청자를 제거하는 경우), "both- 자원 "남은 장비는> = 왼쪽의 요청자 수입니다.

해결하려는 문제의 클래스를보다 명확하게 지정할 수 있다면 그에 대한 대답을 더 세밀하게 지정할 수 있습니다 (아무런 제약없이 명확한 NP 완성 문제가 될 수 있음).하지만 충분한 제약 조건 컴퓨터로 실행 가능하게 만들 수 있습니다!).