백준 1285번: 평범한 배낭(Python,파이썬, knapsack problem, 배낭 문제, DP)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

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

입력으로 주어지는 모든 수는 정수이다.

출력

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

문제 풀이

이 문제는 전형적인 0/1 Knapsack Problem(배낭 문제) 이다.
각각의 물건은 한 번만 선택할 수 있고, 배낭에는 최대 K의 무게까지 담을 수 있다. 목표는 총 가치를 최대로 하는 물건 조합을 찾는 것이다.
Knapsack 문제는 DP(Dynamic Programming)의 대표적인 예제로 알려져 있다.
특정 물건을 선택하느냐 선택하지 않느냐에 따라 최적해가 분기되고, 이전 단계의 최적해를 기반으로 현재 최적해를 구성하는 구조이기 때문이다.
DP 점화식 정의
문제를 DP로 해결하기 위해
dp[i][w] 를 다음과 같이 정의한다.
dp[i][w] = i번째 물건까지 고려했을 때,
배낭의 허용 무게가 w일 때 담을 수 있는 최대 가치
이제 i번째 물건의 무게를 weight, 가치를 value라고 하면 선택의 경우는 두 가지다.
① i번째 물건을 담지 않는 경우
- i번째 물건의 무게가 w를 초과한다면 선택 불가
- 또는 담지 않기로 한 경우
- 최적값은 이전 물건까지의 최적해
```
dp[i][w] = dp[i-1][w]
```
② i번째 물건을 담는 경우
- weight ≤ w 일 때만 가능
- 이때 얻는 가치는
  - 남은 무게(w - weight)에서 얻을 수 있는 최대 가치 + 현재 물건 가치
```
dp[i][w] = dp[i-1][w-weight] + value
```
두 경우 중 더 큰 값을 선택하면 된다.
따라서 최종 점화식은 다음과 같이 정리된다.
```
if weight > w:
    dp[i][w] = dp[i-1][w]
else:
    dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value)
```
구현 설명 (제공된 코드 기준)
- wv_list에 (무게, 가치) 쌍을 저장하고
- dp 테이블을 (N+1) × (K+1) 크기로 초기화한다.
- 이후 i번째 물건, 현재 허용 무게 j에 대해 위의 점화식을 적용하여 테이블을 채운다.
- 마지막으로 dp[N][K]에 전체 물건을 고려했을 때 얻을 수 있는 최대 가치가 저장되므로 이를 출력한다.

✨ 깔끔 핵심 결론

dp[i][w]를 이용한 전형적 0/1 Knapsack 점화식을 그대로 구현한 코드이며
최종 답은 dp[N][K]에 저장된 배낭의 최대 가치다.

정답 코드

import sys

N, K = map(int,sys.stdin.readline().split())

dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

wv_list = [[0,0]]

for _ in range(N):
    wv_list.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,N+1):
    for j in range(1,K+1):
        weight = wv_list[i][0]
        value = wv_list[i][1]

        if weight > j: # j = 현재 가방의 최대 무게
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)

print(dp[N][K])

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

입력

입력으로 주어지는 모든 수는 정수이다.

문제 풀이

이 문제는 전형적인 0/1 Knapsack Problem(배낭 문제) 이다.
각각의 물건은 한 번만 선택할 수 있고, 배낭에는 최대 K의 무게까지 담을 수 있다. 목표는 총 가치를 최대로 하는 물건 조합을 찾는 것이다.

Knapsack 문제는 DP(Dynamic Programming)의 대표적인 예제로 알려져 있다.
특정 물건을 선택하느냐 선택하지 않느냐에 따라 최적해가 분기되고, 이전 단계의 최적해를 기반으로 현재 최적해를 구성하는 구조이기 때문이다.

DP 점화식 정의

문제를 DP로 해결하기 위해
dp[i][w] 를 다음과 같이 정의한다.

dp[i][w] = i번째 물건까지 고려했을 때,
배낭의 허용 무게가 w일 때 담을 수 있는 최대 가치

이제 i번째 물건의 무게를 weight, 가치를 value라고 하면 선택의 경우는 두 가지다.

① i번째 물건을 담지 않는 경우

i번째 물건의 무게가 w를 초과한다면 선택 불가
또는 담지 않기로 한 경우
최적값은 이전 물건까지의 최적해

dp[i][w] = dp[i-1][w]

② i번째 물건을 담는 경우

weight ≤ w 일 때만 가능
이때 얻는 가치는
- 남은 무게(w - weight)에서 얻을 수 있는 최대 가치 + 현재 물건 가치

dp[i][w] = dp[i-1][w-weight] + value

두 경우 중 더 큰 값을 선택하면 된다.

따라서 최종 점화식은 다음과 같이 정리된다.

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

구현 설명 (제공된 코드 기준)

wv_list에 (무게, 가치) 쌍을 저장하고
dp 테이블을 (N+1) × (K+1) 크기로 초기화한다.
이후 i번째 물건, 현재 허용 무게 j에 대해 위의 점화식을 적용하여 테이블을 채운다.
마지막으로 dp[N][K]에 전체 물건을 고려했을 때 얻을 수 있는 최대 가치가 저장되므로 이를 출력한다.

정답 코드

import sys N, K = map(int,sys.stdin.readline().split()) dp = [[0 for _ in range(K+1)] for _ in range(N+1)] wv_list = [[0,0]] for _ in range(N): wv_list.append(list(map(int,sys.stdin.readline().split()))) for i in range(1,N+1): for j in range(1,K+1): weight = wv_list[i][0] value = wv_list[i][1] if weight > j: # j = 현재 가방의 최대 무게 dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value) print(dp[N][K])