Written by Lee Jongseo
on May 22, 2021

Alogrithm[6]:⭐⭐ - Greedy Method(Coin Change Problem, Fractional Kanpsack Problem)

Greedy Method(또는 Greedy Algorithm)

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.

탐욕 알고리즘은 최적해를 계산할 수도 안 할수도 있다. 최적해에 가까운 결과를 나타낸다.

Coin Change Problem(또는 Change-making problem)

Change-making problem

The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money.

문제 해결

coin_list가 주어졌을때, 리스트 내, coin를 이용하여 value를 만들 수 가장 적은 coin(minimum_number)의 수를 찾는 문제.

EX)

[500, 100]이 주어진 경우, 700을 만들 수 있는 coin의 수는 3개.(500원 1개, 100원 2개)

Greedy Algorithm을 이용하여 문제를 해결할 수 있다.

idea: 가장 적은 수를 만들기 위해서는 가치가 높은 coin부터 이용해야 한다.

Python Implementation

coin_list = [10, 50, 100, 500]
value = 8760
def minimum_coins(coin_list, value):
    # 가장 비싼 동전부터 이용해야 한다.
    count = 0
    coin_list.sort(revere=True)
    for coin in coin_list:
        # 각각의 stage에서 최적의 해를 찾는다.
        num_coin = value // coin
        count += num_coin # 최적의 동전의 개수
        value -= (coin * num_coin)
    return count
minimum_coins(coin_list, value)

Fractional Kanpsack Problem

Continuous knapsack problem(Fractional Kanpsack Problem)

the goal is to fill a container (the “knapsack”) with fractional amounts of different materials chosen to maximize the value of the selected materials.

물건 리스트가 주어진다.
물건은 무게와 가치를 가지고 있다.
물건마다 무게와 가치가 다르다.
배낭을 물건으로 채워야 한다.
배낭은 k만큼 무게를 수용할 수 있다.
배낭의 무게 여유분이 물건의 무게보다 작다면 물건의 부분(fraction)만 채울 수 있다.
배낭을 채운 물건의 가치가 최대(maximize)가 되도록 물건을 채워야 한다.

    INPUT: 물건리스트, 배낭의 무게
    OUTPUT: maximum_value

문제 해결

Idea: 무게가 적게 나가면서 가치는 높은 물건 순으로 배낭을 채워야 한다.

주어진 리스트를 효율이 좋운 순서대로 sorting하여 각각의 stage에서 최적의 해를 구한다.

Python Implementation

# (무게, 가치)
L = [
    (10, 10),
    (15, 12),
    (20, 10),
    (25, 8),
    (30, 5),
]

k = 30

def maximum_value(L, k):
    # 효율이 좋은 순서대로 sort한다.
    # x[1] / x[0] : 가치 / 무게 => 무게 1당 가치
    sorted_L = sorted(L, key=lambda x: x[1] / x[0], reverse=True)
    value =  0
    for item in sorted_L:
        if (k >= item[0]):
            value += item[1]
            k -= item[0]
        else:
            fraction = k / item[0]
            value += item[1] * fraction
    return value
    
maximum_value(L, k)

👈 👉 Top