Baekjoon / 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

KnapSack (냅색) 문제

냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나뉜다.

 

담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)

담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)

 

해당 문제는 나누어 지지 않는 문제로 0-1 배낭 문제이다.

 

 

Solution #1

def main(n,m,w_val):
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
    # w_val.sort(key = lambda x: (x[0],x[1]))
    for i in range(n+1): # 물품 수만큼(행)
        for j in range(m+1): # 배낭 최대 무게(열)
            if i==0 or j==0:
                dp[i][j] = 0
            elif w_val[i-1][0] <= j:  # 현재 물품 무게 <= 배낭 최대 무게
                # max(현재 물품의 가치 + dp[이전 물품][배낭 최대 무게(j)-현재 물품 무게]
                # w_val[i-1][0] 무게 / w_val[i-1][1] 가치
                dp[i][j] = max(w_val[i-1][1]+dp[i-1][j-w_val[i-1][0]],dp[i-1][j])
            else:  # 현재 물품 무게 > 배낭 최대 무게
                dp[i][j] = dp[i-1][j]  # 해당 배낭 최대 무게(j)에서 이전 물품까지 최대 가치 합 가져옴.
    return dp[n][m]

n, m = map(int, input().split())

w_val = []

for i in range(n):
    w, v = map(int, input().split())
    w_val.append([w,v])

print(main(n,m,w_val))

dp 결과는 아래와 같다.

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

 

weight_value 리스트를 굳이 정렬하지 않았음에도 무게에 따라 정렬되어(행) dp 결과가 저장된 것을 확인할 수 있다.

 

 

Solution #2

n, m = map(int, input().split())
w_val = [[0, 0]]
dp = [[0 for _ in range (m + 1)] for _ in range(n + 1)]

for _ in range(n):
    w_val.append(list(map(int, input().split())))

# 냅색 문제 풀이
for i in range(1, n + 1):
    for j in range(1, m + 1):
        weight = w_val[i][0]
        value = w_val[i][1]

        if j < weight:
            dp[i][j] = dp[i - 1][j]  # weight보다 작으면 위의 값을 그대로 가져온다
        else:
            dp[i][j] = max(value + dp[i - 1][j - weight], dp[i - 1][j])

print(dp[n][m])

Solution #1 과 같은 동일한 문제 풀이지만, dp 결과가 다른 방식으로 저장되는 코드이다.

Solution #2 의 dp 결과는 아래와 같다.

		0	1	2	3	4	5	6	7
weight	value
6	13		0	0	0	0	0	13	13
4	8		0	0	0	8	8	13	13
3	6		0	0	6	8	8	13	14
5	12		0	0	6	8	12	13	14

 

 

 

Reference

https://gsmesie692.tistory.com/113