while(코인이 있고 instance 해결 안되면) {
Grab the Largest Coin;
if(목표값보다 커지면)
reject the coin
else
add the coin to the change;
if(목표값과 같다면)
instance 해결;
}
//W[i][j] : 정점 i에서 정점 j 사이 weight
void prim(int n, const number W[][], set_of_edges& F){
index i, vnear;
number min;
edge e;
index nearest[2..n];
number distance [2..n];
F=0;
for(i=2;i<=n;i++){
nearest[i]=1;
distance[i]= W[1][i];
}
repeat(n-1 times){
//edge 개수가 n-1개 이기 때문에
min=INF;
for(i=2;i<=n;i++)
if(0<=distance[i]<min){
min = distance[i];
vnear=i;
}
e = edge; // vnear과 nearest[vnear]을 연결하는 edge
add e to F;
distance[vnear]=-1
for(i=2;i<=n;i++)
if(W[i][vnear]<distance[i]){
distance[i] = W[i][vnear];
nearest[i]= vnear;
}
}
}
High level
Y = {v1};
F = 0;
while (instance 해결할 때까지){
V-Y에서 vertex v 고른다,
그 vertex는 v1에서 최단거리를 거진다.
오직 Y에 있는 vertices를 중간지점으로 사용한다.
vertex v를 Y에 추가한다;
edge를 F에 추가한다;
if(Y==V) // 해결
instance is solved;
}
void dijkstra(int n, const number W[][], set_of_edges& F){
index i, vnear;
edge e;
index touch[2..n];
number length[2..n];
F=0;
for(i=2;i<=n;i++){
touch[i]=1;
length[i] = W[1][i];
}
repeat(n-1 times){
//vertices가 n-1개
min=INF;
for(i=2;i<=n;i++)
if(0<=length[i]<min){
min = length[i];
vnear = i;
}
e = edge // touch[vnear]
add e to F;
for(i=2;i<=n;i++)
if(length[vnear] + W[vnear][i] < length[i]){
length[i] = length[vnear]+W[vnear][i];
touch[i] = vnear;
}
length[vnear]= -1; // vnear을 Y에 추가한다.
}
}
Minimize Total Time in the System
EX) t_1 = 5, t_2 = 10, t_3 = 4
[1,2,3] : 5+ 5+10 + 5+10+4 = 39
[3,1,2]: 4+ 4+5 + 4+5+10 =32
Smallest service time first
GA is optimal
Proof)
S : t_1,t_2….,t_i t_i+1,….,t_n → T
S: t_1,t_2,…,t_i+1, t_i,…,t_n → T
X = t_1+…+t_i-1
⇒ 모순 발생!
Maximize the total profit
EX) D= (2,1,2,1) , P= (30,35,25,40)
[2,1] : 35+ 30 = 65
[4,1] : 40+ 30 = 70
Job을 Profit높은 순으로 정렬 후 데드라인에 맞게 선택한다
void schedule(int n, const int deadline[], sequence_of_integer& J){
index o;
sequence_of_integer K;
J=[1];
for(i=2; i<=n; i++){
K = J with i addded according to nondecreasing values of deadline[i];
if (K is feasible)
J=K;
}
}
struct nodetype{
char symbol;
int frequency;
nodetype* left;
nodetype* right;
};
Fractional KSP → Greedy Approach : Select item by Largest profit per weight
0/1 KSP → Greedy X
KNAP(s,Y) :
⇒ Optimal Sol for KNAP(n,W)
만약 (n번째 아이템을 선택 안 할때) → 이 KNAP(n-1,W)의 optimal sol이다.
ex) W=10, P=(10,4,3,5,2), W=(5,4,2,3,2) 일 때
Y = (1, 0, 1, 1, 0)이면 (1,0,1,1)이 W=10, P=(10,4,3,5), W=(5,4,2,3)의 최적해다.
만약 (선택한다면) 이 KNAP(n-1,W-wn)의 optimal sol이다.
시간복잡도 :
문제 크기에 따라 계산시간 다르다