이 탐욕스러운 알고리즘에 대한 반박 예제를 제시하십시오.

Question

이 숙제에 문제가 있습니다. 주된 혼란은 반례에 대한 근거를 밝히지 않은 데서 오는 것이라고 생각합니다.

하자 P1,. . . , Pn은 디스크에 저장된 프로그램입니다. 프로그램 Pi은 Si 메가 바이트의 저장소가 필요하며 디스크 용량은 D 메가 바이트입니다. D 저장의 메가 바이트의 합보다 작은 경우

• 의 (a)는 디스크에 개최 프로그램의 수를 극대화 할 수 있습니다. 입증 또는 이의 예를 제공 : Si

• (b)는 가능한 디스크의 용량을 많이 사용 증가 순으로 프로그램을 선택 욕심쟁이 알고리즘. 증명 또는 반대 예제를 제공 : 명확히하지 죄송합니다 : Si

편집을 감소의 위해 프로그램을 선택 욕심 알고리즘을.

(a) 부분에 대해서는 처음으로 프로그램을 선택하지 않았다고 가정하고 있습니다 (Si). Pa, Pb 및 Pc을 선택하는 경우, 이후에 Sa<=Sb<=Sc을 입력하고, 그 다음에 나갈 방법을 실제로 이해하지 못했으며 (b) 같은 질문을하지만 Si을 입력하십시오.

Answer 1

a) 정리 : 필요한 디스크 공간을 늘려 프로그램을 실행하면 많은 프로그램을 실행할 수 있습니다. 증명 : 증거는 모순이다. 더 많은 것을 실행할 수있는 프로그램을 선택하는 다른 방법이 있다고 가정합니다. 그런 다음이 방법은 최소한 하나의 경우 다른 프로그램 집합을 선택해야합니다. 즉, 선택되지 않은 것보다 더 많은 공간을 필요로하는 최소한 하나의 프로그램을 선택해야합니다. 그러나이 방법은 욕심 많은 알고리즘에 의한 선택과 구별되는 다른 프로그램보다 공간이 덜 필요한 프로그램을 선택했을 수도 있습니다. 이것은이 방법이 욕심 많은 방법보다 낫다는 가정과 모순됩니다. 그러므로 욕심 많은 방법보다 더 좋은 방법은 없습니다. 최적입니다.

b) 정리 : 디스크 공간이 필요한 순서대로 프로그램을 가져가는 것이 가능한 많은 디스크 공간을 사용하는 것은 아닙니다. 증명 : 증거는 예시입니다. 크기가 10 인 디스크와 디스크 공간 6, 5 및 5가 필요한 프로그램을 생각해보십시오. 필요한 디스크 공간이 줄어드는 순서로 프로그램을 사용하면 10 개의 사용 가능한 저장 장치 중 6 개만 사용할 수 있습니다. 반면에 두 개의 프로그램 총 10 개의 유닛에 대해 각각 5 개의 유닛이 필요합니다. 따라서, 욕심 많은 접근 방식은 모든 경우에 최적의 결과를 제공하지 못합니다.