배낭 문제(냅색 문제) - 1 (분할가능한 배낭 문제)

https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C

배낭 문제 - 나무위키

https://www.youtube.com/watch?v=8UVDnahV1eg 

분할 가능한 배낭 채우기 문제

그리디 알고리즘으로 정렬을 해서 무게를 채워주면 된다.

Frational Knapsack Problem

탐욕알고리즘을 이용해서 최적의 해를 구할 수 있다.

def knapsack1(W,w,p):
    n = len(w) - 1
    K = [0] * (n + 1)
    weight = 0
    for i in range(1, n+1):
        weight += w[i]
        K[i] = w[i]
        if (weight > W):
            K[i] -= (weight - W)
            break

    return K

# 지금은 무게와 가치가 가치순으로 내림차순 정렬되어 있지만
# 보통은 안그럴 경우가 더 많다.
w = [0,2,5,8,7,40,13,24]
p = [0,15,12,8,8,7,5,2]

W = 30
K = knapsack1(W, w, p)
print(K, sum(K))
price = 0
for i in range(1, len(K)):
    price += p[i] * K[i]

print("Total price is", price)

 

탐욕 알고리즘은 최적해를 보장하는가?

* 아이템의 분할이 가능하면 Greedy가 최적해를 찾아줌

* 하지만 분할이 가능하지 않다면 -> 최적해가 아닐 가능성이 더 높음