💻 백준 12865번: 평범한 배낭

문제 소개 🧐

N개의 물건과 각 물건의 무게(W)와 가치(V)가 주어진다. 최대 K만큼의 무게를 담을 수 있는 배낭에 물건을 담아, 가치의 합이 최대가 되도록 해야 하는, 아주 유명한 배낭 문제이다.

입력 📝

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

출력 📤

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

나의 풀이 과정 🌊

첫 번째 시도: 단순 DP

Idea: dp[i]를 ‘무게 i일 때의 최대 가치’로 정의하고, dp[i] = dp[i-w] + v 와 같은 점화식을 생각했다. 하지만 이 방식은 한 번 사용한 물건을 또 사용하는 문제가 있었다.

import sys

n, k = map(int, sys.stdin.readline().split())
w_v_dict = {}
for i in range(n):
    w, v = map(int, sys.stdin.readline().split())
    if w_v_dict.get(w) is None:
        w_v_dict[w] = v
    else:
		    # 같은 무게 다른 value 면 더 value가 큰 값만 저장
        w_v_dict[w] = max(w_v_dict[w], v)

dp = [0] * (k+1)

# dp[i] = dp[i-w] + dp[w]

for i in range(1, k+1):
		# 모든 물건에 대해 비교
    for w in w_v_dict.keys():
        if w > i:
		        # 물건의 무게가 더 무거우면 건너뛰기
            continue
        elif i == w:
            dp[i] = max(dp[i], w_v_dict[w])

        if  dp[i] < dp[i-w] + dp[w]:
            dp[i] = dp[i-w] + dp[w]

print(dp[k])

Result: 실패 😭

두 번째 시도: 그리디 알고리즘

Idea: (가치/무게) 비율, 즉 ‘가성비’가 좋은 물건부터 담는 그리디 방식으로 접근했다. 하지만 이 방식은 부분적인 최적해가 전체적인 최적해를 보장하지 않아 실패했다.

import sys
import heapq

n, k = map(int, sys.stdin.readline().split())
w_v_list = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

ratio_list = list(map(lambda x: (x[0]/x[1], x[0], x[1]), w_v_list))  # 무게 / 밸류 비율로 리스트 만들고
r_w_v_list = []

for i in range(n):
    heapq.heappush(r_w_v_list, ratio_list[i])  # 무게 / 밸류 비율 기준으로 우선순위 큐 (값이 낮을수록 챙겨야 함)

total_weight, total_val = 0, 0
while r_w_v_list:
    r, w, v = heapq.heappop(r_w_v_list)
    print(r, w, v)
    if total_weight + w > k:
        continue
    total_weight += w
    total_val += v

print(total_val)

Result: 실패 😭

세 번째 시도: 올바른 DP ✨

Idea: 각 물건을 한 번만 사용하도록 보장하기 위해, DP 테이블을 뒤에서부터 갱신했다. 안쪽 루프를 최대 무게 K부터 현재 물건의 무게 w까지 역순으로 순회하며 dp 테이블을 갱신하면, dp[i-w]는 아직 현재 물건이 반영되지 않은 상태이므로 중복 계산을 피할 수 있다.

Code:

import sys

n, k = map(int, sys.stdin.readline().split())
w_v_list = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [0] * (k+1)

for w, v in w_v_list:
    for i in range(k, w-1, -1): # 뒤에서부터 순회하여 중복 방지
        dp[i] = max(dp[i] , dp[i-w] + v)

print(dp[k])

Result: 성공! ✅

배운 점 및 느낀 점 ✍️

  • 냅색(Knapsack) 문제의 기본 원리와 왜 단순 그리디로 풀 수 없는지를 명확히 이해하게 되었다.
  • DP 테이블을 갱신하는 순서(앞 → 뒤 vs 뒤 → 앞)에 따라 문제의 조건(물건 중복 사용 가능/불가능)을 다르게 구현할 수 있다는 점이 인상 깊었다.
  • 냅색 문제란?
    제한된 무게 용량을 가진 배낭에 물건들을 담을 때, 각 물건의 가치와 무게를 고려하여 최대 가치를 얻도록 물건을 선택하는 문제