qkrclrl701   2년 전

최대 유량 알고리즘은 아직 공부를 안해서 그냥 제 생각대로 풀었는데요,

자신을 잡아먹는 상어가 많은 순으로 상어들을 정렬하고, 그 순서대로 각 상어들이 greedy하게 최대한 많은 상어를 먹도록 구현하였는데요

만약에 상어 A를 잡아먹는 상어의 수가 상어 B를 잡아먹는 상어의 수보다 크면,

상어 A가 먼저 자신보다 약한 상어들을 다 잡아먹어 버리니, 상어 A가 다른 상어들을 잡아먹기 전에 B가 A를 잡아먹어 버리는 경우가 없어져서 최적의 해를 구할 수 있을거라고 생각했는데요, 어떠한 경우에 최적의 해를 구하지 못하는 것일까요?? 

qkrclrl701   2년 전

반례가 생각이 났습니다.

상어 4가 0 1 2 3 을 잡아먹을 수 있고,

상어 5가 0를 잡아먹을 수 있는 상황을 가정하면

상어 4가 0, 1을 먼저 잡아먹어 버리므로 상어 5가 0을 못잡아 먹어서 낭비가 일어나게 되네요.

댓글을 작성하려면 로그인해야 합니다.