매순간 최적이라고 생각되는 경우를 선택하는 방식

문제 1

지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.

가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능

탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

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
    
 min_coin_count(4720, coin_list) // (31, [[500, 9], [100, 2], [50, 0], [1, 20]])

문제 2

무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
각 물건은 무게(w)와 가치(v)로 표현될 수 있음
물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음

1. data_list를 가치 / 무게값으로 변경후 내림차순 정렬하여 높은 가치를 가진 물건을 먼저 가방에 넣는다.

2. 물건이 현재의 무게 제한(capacity)을 초과하는 경우 물건을 쪼개서 가방에 넣어준다.

3. 물건이 무게 제한에 안걸리면 무게제한을 물건 무게만큼 빼준다.

data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

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
    
get_max_value(data_list, 30) // (24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])