[백준] 12865 아주 평범한 배낭 Python

1. 문제 

최대 K 만큼의 무게만을 넣을 수 있는 배낭에
무게 Weight 와 가치 Value 를 가지는 N 개의 물건이 있다
배낭에 넣을 수 있는 물건들의 가치의 최대값 찾기 

2. 제한

시간 제한 2초, 메모리 제한 512MB
물품의 수 1 <= N <= 100
버틸 수 있는 무게 1 <= K <= 100,000
각 물건의 무게 1 <= W <= 100,000 
해당 물건의 가치 0 <= V <= 1,000

3. 알고리즘 분류

* 다이나믹 프로그래밍 

* 배낭 문제 

4. 접근 방식

Knapsack Problem 을 한 번 공부했다 Knapsack Problem 개념 정리 

물건을 쪼갤 수 있다는 언급은 없어서 0-1 Knapsack 방식으로 접근했다 

예시 입력을 기준으로 - n = 4, k = 7, 물건 (6, 13), (4, 8), (3, 6), (5, 12) 일 때

물건을 무게 오름차순으로 다시 정렬하고 (3, 6), (4, 8), (5, 12), (6, 13) <- 이건 내가 하고 싶어서 함!

아래와 같이 이전의 가치와, 현재 물건을 넣었을 때의 가치를 비교/ 갱신하며 표를 채웠다 

 

X 부분이 값을 갱신한 부분이다

8을 예시로 들면, 이전 값 6과 남은 배낭 용량 (4-3) 에서 최적의 가치 + 현재 물건의 가치 8 를 비교한다

	0	1	2	3	4	5	6	7
1번 물건	0	0	0	6	6	6	6	6
2번 물건	0	0	0	6	8	8	8	8
3번 물건	0	0	0	6	8	12	12	14
4번 물건	0	0	0	6	8	12	13	14

 

5. 전체 코드

첫번째 방법 - 2차원 배열로 풀기 

# 최대 K만큼의 무게만을 넣을 수 있는 배낭에
# 무게 Weight와 가치 Value를 가지는 N개의 물건이 있다
# 배낭에 넣을 수 있는 물건들의 가치의 최대값 찾기 

def knapsack(weight, value, k):
    n = len(value) # dp 배열, 반복문에서 간단하게 사용하기 위해 변수 생성 
    # k+1 행 n+1 열로 DP 테이블 초기화
    dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
    
    # dp[i][w] 는 i번째 물건까지 고려 && 남은 용량 w 일 때의 최대 가치
    # weight, value 는 0부터 시작, dp index 는 i-1, w-weight[i-1] 로 계산
    for i in range(1, n+1):
        for w in range(1, k+1):
            # 현재 물건 weight[i-1] 을 배낭에 넣을 수 있을 때 
            # 현재 물건을 넣지 않은 경우 이전 단계 dp[i-1][w] 그대로
            # 물건을 넣었을 때 남은 배낭 용량에서 최적의 가치 + 현재 물건의 가치 
            if weight[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])
            else:
                # 물건을 넣을 수 없으면 그대로 이전 값 
                dp[i][w] = dp[i-1][w]

    return dp[n][k]

if __name__ == '__main__':
    # 물건 개수와 배낭 무게 입력 받기 
    n, k = map(int, input().split())

    weight = [] 
    value = [] 

    # 물건의 무게와 가치 입력 받고 긱 배열에 추가해주기 
    for i in range(n):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)

    # n, k = 4, 7
    # weight = [2, 3, 4, 5]
    # value = [3, 4, 5, 8]

    # 최대 가치 출력 
    max_value = knapsack(weight, value, k)
    print(max_value)

 

두번째 방법 - 일차원 배열로 풀기

이 방법은 일차원 배열로 dp 값을 갱신했고, 갱신하는 과정에서

for 문을 역순으로 돌아 갱신되기 전의 dp[i-weight] 를 참고할 수 있게 했다 

이런 좋은 방법을 공유해 주신 로건님에게, 다시 한 번 고맙습니다!

https://studyiwthme.tistory.com/158

def knapsack(items, k):
    dp = [0] * (k+1)

    # k 부터 weight 까지 역순으로, items 에서 weight, value 를 꺼내기
    # 이전 가치 dp[i] 와 남은 배낭 용량에서 최적의 가치 + 현재 가치 를 비교한다 
    # 역순으로 넣어주는 이유는 갱신되기 전의 dp[i-weight] 를 참고하기 위해서
    for weight, value in items:
        for i in range(k, weight-1, -1):
            dp[i] = max(dp[i], dp[i-weight] + value)

    return dp[k]

# input 새로 정의
import sys
input = lambda: sys.stdin.readline().strip()

n, k = map(int, input().split())
# 파이썬 컨프리헨션으로 for 문 간단하게 만들어서 items 을 tuple 형태로 입력 받기
items = [tuple(map(int, input().split())) for _ in range(n)]

print(knapsack(items, k))

 

확실히 일차원 배열로 풀었더니 메모리가 확 줄어들었다