최소 신장 트리 연습문제

연습문제

n개의 항목집합 S의 각 항목 i는 양의 이득 bi와 양의 무게 wi로 이루어졌다. 주어진 무게 W를 넘지 않으면서 최대 이득이 되는 S의 부분집합을 계산하는 효율적인 탐욕 알고리즘 Fractional-knapsack(S,W)을 작성하라

Alg fractionalKnapsack(S,W)

1. for dach i to S{
    xi = 0
    vi = bi/wi  //무게에 따른 효율
}
2. w = 0  
3. Q = a priority queue contaning all the items of S using vi as keys
4. while (w < W){
    i = Q.removeMin() //왜 remove min인진 모르겠지만 고효율 부터 뽑아서 넣는다.
    xi = min(wi,W-w) // 무게가 넘치면 안쓴다.
    w = w + xi
}
5. return

S = {a,b,c,d,e,f,g}를 다음과 같은 (이득, 무게)를 가진 개체들의 모음이라 하자. a:(12,4), b:(10,6), c:(8,5), d:(11,7), e:(14,3), f:(7,1), g:(9,6)

1. 배낭이 최대 18의 무게를 지탱할 수 있다고 가정하고 부분적 배낭 문제(물체를 조각낼 수 있다 > 가장 효율 좋은 것 순서대로 넣으면 되는 그리드 문제)라는 전제 하에 S에 대한 최적해를 구해라

• f,e,a,b, 4 of c로 총 무게 18, 총 이득 49.4이다.

2. 이 문제를 0-1 배낭 문제(물건을 분해할 수 없어서 무게를 생각하고 넣어야 된다.)로 전제하고 최적해를 다시 구하라

• f,e,a,b로 총 무게 18, 총 이득 43이다.