백준 12865. 평범한 배낭

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

1. 복잡한...재귀 풀이

N, K = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
# 무게 W 가치 V
max_v = -1
now_v = 0
now_w = 0

def f(idx):
    global max_v, now_v, now_w

    # 모든 아이템을 다 탐색한 경우 -> 최댓값 갱신
    if idx == N:
        max_v = max(max_v, now_v)
        return

    # 현재 아이템을 넣을 수 있어 넣는 경우
    if now_w + arr[idx][0] <= K:
        now_v += arr[idx][1] # 넣을 수 있으면 넣고 가치 더하기
        now_w += arr[idx][0] # 근데 무게도 더하기
        f(idx+1) # 다음 아이템 진행
        now_v -= arr[idx][1] # 넣은 아이템 제거(백트래킹)
        now_w -= arr[idx][0]

    # 현재 아이템을 넣지 않는 경우
    f(idx + 1)

f(0)
print(max_v)

2. 간단한 재귀 풀이

def f(idx, w, v):
    global max_v
    if w > K:
        return

    if idx == N:
        max_v = max(max_v, v)
        return

    f(idx + 1, w + arr[idx][0], v + arr[idx][1])
    f(idx + 1, w, v)

N, K = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
max_v = 0
f(0,0,0)
print(max_v)

3. dp 풀이

import sys
input = sys.stdin.readline

N, K = map(int,input().split()) # 물건의 수, 버틸 수 있는 무게
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*(K+1) for _ in range(N+1)]

for i in range(1,N+1): # 물건의 인덱스
    for j in range(1,K+1): # 배낭이 현재 견딜 수 있는 무게 한도(0은 의미 없으므로 생략하고 1~K까지)
        if j >= arr[i-1][0]: # 현재 물건(i-1)의 무게가 현재의 무게 한도를 초과하지 않을 때 -> 넣을 수 있음!
            # 현재 물건의 가치+물건을 넣은 후 남은 공간에서 얻을 수 있는 최대 가치 vs 현재 물건을 넣지 않았을 때의 최대 가치
            dp[i][j] = max(arr[i-1][1]+dp[i-1][j-arr[i-1][0]], dp[i-1][j])
        else: # 현재 물건을 넣지 못하니 그대로 복붙(유지)
            dp[i][j] = dp[i-1][j]

print(dp[N][K]) # N개의 물건을 고려했을 때, 배낭의 최대 무게가 K일 때의 최대 가치

4. 인프런 강사님 풀이 - 탑다운

# recur이 반환하는 값 = 현재까지 고려한 물건들 중에서 특정 무게 w로 만들 수 있는 최대 가치

def recur(idx, w):
    global ans
    
    # 최대무게를 초과한 경우 -> 제외시켜주기
    if w > m: 
        return -9999999
	
    # 모두 탐색했을 경우, 더이상 추가할 수 있는 물건이 없으므로 0 반환
    if idx == n:
        return 0
        
	# 이미 한번 계산된 값이 있으면 해당 값을 재사용 (메모이제이션) -> visited 대체가능
    if dp[idx][w] != -1:
        return dp[idx][w]
	
    # 넣었을 때 가치 vs 안 넣었을 때 가치 -> 최댓값 dp 테이블에 갱신
    dp[idx][w] = max(recur(idx + 1, w + arr[idx][0]) + arr[idx][1], recur(idx + 1, w))

    return dp[idx][w]


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(n)]

dp = [[-1 for _ in range(m+1)] for j in range(n)] # dp 테이블 범위에 주의할 것

ans = recur(0, 0) # 인덱스 0(처음)부터 시작해서 모든 물건을 다 탐색한 후 가질 수 있는 가장 큰 가치 반환

print(ans)

5. 인프런 강사님 풀이 - 바텀업

import sys

input = sys.stdin.readline
n, m = map(int, input().split())

# y축 = 물건의 무게, 가치  / x축 = 배낭의 무게
# +1 달아서 0,0은 0으로 추가 (물건을 못넣을 때)
dp = [[0] * (m + 1) for _ in range(n + 1)]

for y in range(1, n + 1):  # 모든 물건 탐색
    weight, value = map(int, input().split())
    for x in range(1, m + 1):  # 남은 가방 무게가 x일 때

        # (= 현재 남은 가방의 무게보다 물건의 무게가 더 클 때)
        # 물건을 담을 수 없을 때  (전에 넣어뒀던 무게로 유지)
        if x < weight:
            dp[y][x] = dp[y - 1][x]

        # 물건을 담을 수 있을 때 (x보다  무게가 작거나 같을 때)
        else: # 전에 넣어뒀던 무게 vs 물건을 넣어서 전 상태에서 무게를 차감하고 가치를 더했을 때의 값
            dp[y][x] = max(dp[y - 1][x], dp[y - 1][x - weight] + value)

print(dp[n][m])