탐욕 알고리즘(Greedy) - 물건 가방 담기 문제

이번 문제에서는 물건과 그에 대한 가치가 주어지고, 가방의 최대 한도 무게가 주어졌을 때, 최대한 높은 가치의 물건을 담기 위한 문제이다.

 

이는 동전 지불 문제에서 확장된 문제이며, 풀이 접근은 아래와 같다.

 

	1	2	3	4
무게	10	20	30	40
가치	10	10	15	40

위와 같이 물건의 무게와 가치가 있다고 하자.

먼저, 무게는 다 다르고, 가치도 다른데, 어떤 물건이 더 가치있는 지 어떻게 판단할까?

가치 / 무게를 하면 무게에 대한 가치 비율을 알 수 있지 않을까?

 

2번과 3번 물건에 대해 계산을 해보자

2번 -> 10 / 20  3번 -> 15 / 30

2번, 3번 물건은 결과적으로 가치가 같은 물건임을 알 수가 있다.

 

 

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


def maxBagValue(data_list , capacity):
	# 가치/무게의 값을 기준으로 정렬 내림차순 실행
    data_list = sorted(data_list, key = lambda x:x[1]/[0], reverse=True)
    
    # 전체 가치를 결과로 출력하기 위함
    tot_val = 0 
    
    # 물건 별 세부 가치를 알기 위한 상세정보
    det = []
    
    for data in data_list:
    	# 가방 무게가 현재 물건 무게보다 큰 경우
        if capacity >= data[0]:
            capacity -= data[0] #가방무게에서 물건 무게 빼기
            tot_val += data[1] #물건의 가치 더하기
            det.append([data[0],data[1],1]) #물건, 가치, 비율
            
        else :
        	fraction = capacity / data[0]
        	tot_val += data[0] * fraction
            det.append( [data[0],data[1],fraction] ) 
            break
        return tot_val, det
        
print(maxBagValue(data_list, 100))