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

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의 대답을 좋아합니다.

사용자를 한 번에 하나씩 가져 가면 문제를 해결할 수 있습니다. 즉, 첫 번째 사용자는 필요한 것이 있거나 적합하지 않은 경우 워크 스테이션에 도착하도록합니다. 즉, 다음 사용자는 "프린터가 필요하지만 프린터가있는 유일한 워크 스테이션에는 이미 스캐너가 있습니다". 프린터와 스캐너를 사용하여 워크 스테이션에 넣습니다.

그것이 당신이 원하는 것이 아니라면 --- 실제로, 당신은 하루 종일 방을 사용할 수있는 사용자를 위해 하루 전에 미리 계획하고 있으며, 알고 싶은 것은 "실현 가능 여부"---- 그런 다음 나는 I입니다. 'D를 살펴보십시오 http://en.wikipedia.org/wiki/np-complete 이것에 너무 많은 시간을 보내기 전에.

Answer 2

나중에 필요한 것을 추가하면 방에 1 인 1을 추가 할 때 어떨까요? 당신은 그가 프린터가 필요하다는 것을 알았고, 당신은 방 안에있는 새로운 사람들과 현재 가지고있는 사람들에 프린터를 추가합니다.

따라서 새로운 사람을 추가하면 사람들의 필요가 아니라 현재 상태를 확인합니다.

Answer 3

당신은 평범한 세트가 아니라 멀티 세트를 말하고 있습니다. 어쨌든, 당신이 제공하는 유일한 예에서와 같이, 객실의 모든 사람이 단일 자원이 필요하고 두 가지 자원 만 중요하다면 Life는 매우 쉽습니다. 장비 배열을 풍부하게 정렬하십시오 (스캐너 전용, 프린터 전용, 둘 다- 제공하는 항목은 중요하지 않습니다!), 각 리소스에 대해 최소 (가용, 요청 된)만큼 많은 1 개의 원료 전용을 할당하고 (해당 요청자를 제거), "둘 다 자원 "장비는> = 왼쪽 요청자 수입니다.

어떤 클래스의 문제를 해결하고자하는지 더 명확하게 지정할 수 있다면, 그에 따라 대답을 날카롭게 할 수 있습니다 (제약 조건이 없으면 다른 답변이 제안한 것처럼 NP- 완료 문제가 될 것입니다. 그러나 충분한 제약 조건으로 계산적으로 만들 수 있습니다. 실현 가능 한!).