[Python] 배송비 절약 문제 동적프로그래밍 구현

이번 글에서는 파이썬 언어를 사용하여 배송비 절약 문제를 구현합니다.

이때 동적프로그래밍 기법을 사용합니다.

1. 배송비 절약 문제

물건의 개수, 배송가능한 무게제한, 물건의 무게와 가치가 주어졌을 때,

한번에 배송할 수 있는 최대의 물건 가치가 얼마인지 구하시오.

2. 코드 구현

주어지는 입력 정보

# 물건 개수
item_num = 5
# 배송 제한 무게
limit_weight = 10
# 물건의 무게
w_lst = [2,1,1,4,4]
# 물건의 가치
v_lst = [34,686,668,678,560]

배송 가능 최대 물건 가치 저장 리스트 생성

D = [[0]*(limit_weight+1) for _ in range(item_num)]

물건별로 탐색하며 0~배송 제한 무게값 별로 최대 가치를 계산

배송 제한 무게가 10일경우 0~9 무게에 대한 최대 배송 가치를 계산하는 이유는,

이후 물건이 무게가 3일경우 비게되는 무게 7에 대해서 가장 높은 가치를 가지는 값을 찾기 위해서이다.

for item_n in range(item_num):
        # 현재 물건의 무게와 가치 받아오기
        now_item_w, now_item_v = w_lst[item_n-1],v_lst[item_n-1] # 물건1번의 인덱스는 0이기에 -1 취하기
        
        # 무게0 부터 무게 리미트까지 순차로 증가하면서 item이 들어갈 수 있나 검사
        for weight_x in range(limit_weight+1): # 무게 n까지 검사해야해서 +1 취하기
            # 아이템의 무게가 조건 무게보다 크다면
            # 이전 물건의 값 계승
            if now_item_w > weight_x:
                if item_n != 0: # 아이템 번호가 0일경우 무시(계승할 이전 물건이 없음)
                    D[item_n][weight_x] = D[item_n-1][weight_x]
            else: # 아이템의 무게보다 조건 무게가 크거나 같다면
                if item_n == 0: # 첫 물건(인덱스0)일 경우는 그 물건의 가치 삽입
                    tmp = now_item_v
                else: # "이전 물건 가치" "현재 물건 가치+남은무게의 이전물건 가치" 중 큰것 삽입
                    tmp = max(D[item_n-1][weight_x], D[item_n-1][weight_x-now_item_w]+now_item_v)
                D[item_n][weight_x] = tmp

3. 코드 종합

# 중간 과정을 점검하기 위한 프린트 코드
# 실제로 짜실때는 해당 구문을 삭제하세요
def print_m(m):
    for x in m:
        print(x)
    print()

# 물건 개수, 무게 제한, 물건 무게 리스트, 물건 가치 리스트
def func(item_num,limit_weight,w_lst,v_lst):
    # 배송가능한 최대가치 저장용 이중리스트
    D = [[0]*(limit_weight+1) for _ in range(item_num)]
    print_m(D) # 진행과정 출력해보기 => 추후 삭제 필요
    
    # 각 물건별로 탐색
    for item_n in range(item_num):
        # 현재 물건의 무게와 가치 받아오기
        now_item_w, now_item_v = w_lst[item_n-1],v_lst[item_n-1] # 물건1번의 인덱스는 0이기에 -1 취하기
        
        # 무게0 부터 무게 리미트까지 순차로 증가하면서 item이 들어갈 수 있나 검사
        for weight_x in range(limit_weight+1): # 무게 n까지 검사해야해서 +1 취하기
            # 아이템의 무게가 조건 무게보다 크다면
            # 이전 물건의 값 계승
            if now_item_w > weight_x:
                if item_n != 0: # 아이템 번호가 0일경우 무시(계승할 이전 물건이 없음)
                    D[item_n][weight_x] = D[item_n-1][weight_x]
            else: # 아이템의 무게보다 조건 무게가 크거나 같다면
                if item_n == 0: # 첫 물건(인덱스0)일 경우는 그 물건의 가치 삽입
                    tmp = now_item_v
                else: # "이전 물건 가치" "현재 물건 가치+남은무게의 이전물건 가치" 중 큰것 삽입
                    tmp = max(D[item_n-1][weight_x], D[item_n-1][weight_x-now_item_w]+now_item_v)
                D[item_n][weight_x] = tmp
        print_m(D)
    # 저장용 이중리스트의 마지막 값(모든 셀에 대해서 계산된 가장 큰 값이다) 반환
    return D[-1][-1]


### 코드 메인 ###

item_num = 5
limit_weight = 10
w_lst = [2,1,1,4,4]
v_lst = [34,686,668,678,560]

print(func(item_num,limit_weight,w_lst,v_lst))