탐욕 알고리즘

• 현재 상황에서 가장 좋아 보이는 답을 선택하는 방법

탐욕 알고리즘 vs. 동적 알고리즘

탐욕 선택	동적 프로그래밍
하위 문제를 풀지 전에 선택을 한다.	하위 문제를 풀고나서 선택을한다.
항상 하나의 문제만을 고려한다.	동시에 여러 개의 하위 문제를 고려한다.

가중 무방향성 그래프

Weighted undirected graph

• $G=(V,E)$
• 간선 집합에 속하는 각 간선은 $(u,v)$는 $w(u,v)$을 가진다.

신장트리 (Spanning Trees)

• 트리가 그래프 G의 모든 정점을 포함할 때 그래프 G에 속하는 트리의 간선을 선택한 것

최소신장트리 (Minimum Spanning Trees)

• 신장트리의 비용
  $w(T) = \sum_{(u,v)\subseteq T} w(u,v)$
  각 각의 트리를 만들고 그 트리의 가 각 의 웨이트 값을 더하여서 최소값이 무엇이냐?
• 일반적인 MST
  • 최소신장트리는 한번에 하나의 간선이 늘어난다.
  • 간선 (u,v)을 집합 A에 추가하고 $A\cup{(u,v)}$가 최소신장트리의 일부가 되는지 확인한다.

프림 알고리즘

정점의 최선값을 선택하여 MST문제를 해결하는 알고리즘

• 집합 A에 속하는 간선은 항상 트리를 형성한다.
• 트리는 임의의 root 정점r에서 시작하며 정점의 집합 V에 속하는 모든 정점을 포함할 때 까지 확장한다.
• 각 단계에서 가벼운 간선이 트리에 추가된다.
• 따라서, 알고리즘이 종료되면, 최소신장트리가만들어진다.

쿠루스칼 알고리즘

간선의 가중치값을 정렬하여 MST 문제를 해결하는 알고리즘

문제

coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse=True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]
data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)

def get_max_value(data_list,capacity):
    data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0
    details = list()

    for data in data_list:
        if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value += data[1]
            details.append([data[0],data[1],1])
        else:
            fraction = capacity/data[0]
            total_value += data[1] * fraction
            details.append([data[0],data[1],fraction])
            break
    return total_value,details

if __name__ == "__main__":
    # print(min_coin_count(4720, coin_list))
    print(get_max_value(data_list,30))