BOJ) 평범한 배낭

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

12865번: 평범한 배낭

 

오랜만에 알고리즘 문제를 풀다 처음 마주친 "냅색 알고리즘"을 이용해 풀어야하는 문제이다.

 

그리디 알고리즘을 생각했으나 조금만 생각해보면 그리디는 최적의 해를 구할 수 없게된다.

 

우선 냅색 알고리즘은 

물건을 쪼개어 부분적으로 담을 수 있는 경우를 고려하거나 또는 각 물건을 선택하거나 선택하지 않았을 때를 고려하는 경우 사용할 수 있는 알고리즘이다.

 

이 문제의 경우는 "물건을 선택하거나, 선택하지 않았을때"에 해당되므로 냅색 알고리즘을 사용해 풀어볼 수 있다.

 

각 물건을 반복문으로 돌며 해당 물건을 배낭에 넣을 것인지, 혹은 넣지 않을 것인지를 생각해주어야한다.

		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

 

위 표를 보면 조금 더 쉽게 생각해볼 수있다.

물건을 배낭에 담을 때 위와 같은 조건으로 살펴보아야한다.

1. 현재 배낭의 최대 무게보다 현재 물건(넣을 물건)의 무게가 더 크다면 이전 배낭을 들고간다.

2. 현재 배낭의 최대 무게보다 현재 물건의 무게가 더 작다면,

2-1. 이전 배낭의 가치

2-2. 현재 물건과 현재 배낭에서 현재 물건의 무게를 뺀 가치

3. 2-1과 2-2중 최대값을 저장한다.

 

즉

물건의 무게가 현재 배낭의 최대 무게보다 크다면

dp[i][j] = dp[i-1][j]
# 이전 배낭

 

물건의 무게가 현재 배낭의 무게보다 작다면

dp[i][j] = max(v + dp[i-1][j-w], dp[i-1][j]

가 된다.

 

import sys

input = sys.stdin.readline

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

arr = [[0, 0]]

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

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(1, n + 1):
    for j in range(1, k+1):
        w = arr[i][0]
        v = arr[i][1]

        if w > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v + dp[i-1][j-w])

print(dp[n][k])

 

한편, 현재 물건을 담는다/담지 않는다.에서 dfs를 떠올려 한 번 작성해보았다.

 

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
arr = []

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


def dfs(idx, weight, value):
    if idx >= n or weight > k:
        return value

    # 물건을 넣는 경우와 넣지 않는 경우를 나누어 계산
    case1 = dfs(idx + 1, weight + arr[idx][0], value + arr[idx][1])
    case2 = dfs(idx + 1, weight, value)

    # 가치의 최댓값 반환
    return max(case1, case2)


answer = dfs(0, 0, 0)
print(answer)

 

 

아쉽지만 시간초과가 발생했다.