DP: Unbounded Knapsack

좋아! Unbounded Knapsack 문제는 아주 자주 나오는 동적 계획법(DP) 문제 중 하나야.
0/1 Knapsack과 비슷하지만 아이템을 여러 번 쓸 수 있다는 점이 핵심이야.
아래에 직관, 차이점, 예제, 코드까지 정리해서 설명해줄게.

---

🎯 1. 문제 정의: Unbounded Knapsack

무게 제한이 있는 가방이 있고,
각각의 아이템은 **무게(w[i])**와 **가치(v[i])**를 가지고 있음.
각 아이템은 무제한으로 여러 번 선택할 수 있음.
제한된 총 무게 안에서 가장 높은 총 가치를 구하라.

---

🎒 2. 차이점: 0/1 vs. Unbounded

구분

 

구분	0/1 Knapsack	Unbounded Knapsack
아이템 사용	한 번만 사용 가능	여러 번 사용 가능 (무한)
반복 방식	for i in range(n) → for w in reversed(...)	for i in range(n) → for w in **정순**

---

🧠 3. 예시 문제

weights = [2, 3, 4] values = [3, 4, 5] W = 6 # 배낭의 최대 무게

• 무게 2, 3, 4짜리 아이템이 있고,
• 각각 가치는 3, 4, 5
• 이걸 무제한으로 써서 총 가치 최대를 만들어야 함

---

✅ 4. Python 코드 (1D DP)

def unbounded_knapsack(weights, values, W):
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        for w in range(weights[i], W + 1):  # 정순으로 돌아야 여러 번 쓸 수 있음
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

---

📈 5. 동작 설명

• dp[w]: 무게 w일 때 만들 수 있는 최대 가치
• dp[w - weights[i]] + values[i]
  → 현재 아이템을 한 번 더 선택하는 효과
  (즉, 이전 상태에서 이 아이템 하나 더 추가)

---

🧪 예시 시뮬레이션 (W = 6)

• 2kg짜리 아이템(가치 3) 3개 넣으면 6kg, 총 가치 9
• 3kg짜리 2개 넣으면 6kg, 총 가치 8
• 4kg짜리 + 2kg짜리 넣으면 6kg, 총 가치 8

→ 정답은 9 ✅

---

🔁 보너스: 완전탐색(재귀 + 메모이제이션) 형태도 가능

원하면 그 방식도 추가로 알려줄 수 있어!

---

🔑 핵심 요약

항목	내용
핵심 특징	각 아이템을 무한히 선택 가능
반복 순서	정순 (range(w, W + 1))
상태 정의	dp[w] = 무게 w에서의 최대 가치
대표 문제	Coin Change (조합), Rod Cutting, Word Break 등

✅ 1. Brute Force (완전탐색 DFS)

# 완전탐색 DFS 방식: 모든 가능한 조합을 재귀적으로 탐색
# 시간 복잡도: O(2^m), 공간 복잡도: O(m)
# m은 배낭 용량
def dfs(profit, weight, capacity):
    return dfsHelper(0, profit, weight, capacity)

def dfsHelper(i, profit, weight, capacity):
    # 모든 아이템을 다 본 경우
    if i == len(profit):
        return 0

    # 현재 i번째 아이템을 선택하지 않는 경우 (다음 아이템으로 넘어감)
    maxProfit = dfsHelper(i + 1, profit, weight, capacity)

    # 현재 i번째 아이템을 선택하는 경우 (무제한 선택 가능 → 다시 i번째 탐색)
    newCap = capacity - weight[i]
    if newCap >= 0:
        p = profit[i] + dfsHelper(i, profit, weight, newCap)
        maxProfit = max(maxProfit, p)  # 선택하는 경우와 안 하는 경우 중 최대값 저장

    return maxProfit

---

✅ 2. Memoization (Top-down + DP 캐시)

# 메모이제이션을 이용한 Top-Down 방식
# 시간: O(n*m), 공간: O(n*m)
def memoization(profit, weight, capacity):
    N, M = len(profit), capacity
    # 캐시 배열: [아이템 인덱스][남은 용량] → -1로 초기화
    cache = [[-1] * (M + 1) for _ in range(N)]
    return memoHelper(0, profit, weight, capacity, cache)

def memoHelper(i, profit, weight, capacity, cache):
    # 아이템을 다 확인한 경우
    if i == len(profit):
        return 0
    # 이미 계산한 경우 캐시에서 꺼내서 반환
    if cache[i][capacity] != -1:
        return cache[i][capacity]

    # 현재 아이템을 선택하지 않는 경우
    cache[i][capacity] = memoHelper(i + 1, profit, weight, capacity, cache)
    
    # 현재 아이템을 선택하는 경우
    newCap = capacity - weight[i]
    if newCap >= 0:
        p = profit[i] + memoHelper(i, profit, weight, newCap, cache)
        cache[i][capacity] = max(cache[i][capacity], p)  # 두 경우 중 최대값

    return cache[i][capacity]

---

✅ 3. Bottom-Up DP (2차원 배열)

# 바텀업 방식의 DP (2차원 배열 사용)
# 시간: O(n*m), 공간: O(n*m)
def dp(profit, weight, capacity):
    N, M = len(profit), capacity
    dp = [[0] * (M + 1) for _ in range(N)]  # dp[i][c]: i번째 아이템까지 고려했을 때, 용량 c일 때 최대 이익

    # 첫 번째 아이템에 대해 초기값 채우기
    for c in range(M + 1):
        if weight[0] <= c:
            # (c // weight[0]) * profit[0] → 같은 아이템을 몇 번 넣을 수 있는지 계산
            dp[0][c] = (c // weight[0]) * profit[0] 

    # 나머지 아이템들 처리
    for i in range(1, N):
        for c in range(1, M + 1):
            # 현재 아이템을 선택하지 않은 경우 (위의 값)
            skip = dp[i - 1][c]
            # 현재 아이템을 선택하는 경우 (같은 행을 사용 → 무한 사용 가능)
            include = 0
            if c - weight[i] >= 0:
                include = profit[i] + dp[i][c - weight[i]]
            dp[i][c] = max(include, skip)  # 더 큰 값을 선택
    return dp[N - 1][M]  # 전체 용량에서의 최대 이익 반환

---

✅ 4. 메모리 최적화된 DP (1차원 배열)

# 메모리 최적화 버전: 한 줄만 유지하는 방식 (1차원 배열)
# 시간: O(n*m), 공간: O(m)
def optimizedDp(profit, weight, capacity):
    N, M = len(profit), capacity
    dp = [0] * (M + 1)  # dp[c]: 용량 c일 때 최대 이익

    for i in range(N):
        # 현재 행을 새로 만들고 갱신 (이전 dp를 기반으로 계산)
        curRow = [0] * (M + 1)
        for c in range(1, M + 1):
            # 현재 아이템을 선택하지 않은 경우
            skip = dp[c]
            include = 0
            if c - weight[i] >= 0:
                # 이전과 다르게 curRow 사용 → 같은 아이템 여러 번 고려 가능
                include = profit[i] + curRow[c - weight[i]]
            curRow[c] = max(include, skip)
        # dp 갱신
        dp = curRow
    return dp[M]  # 전체 용량에서 최대 이익 반환

---

🧠 핵심 비교 요약

방식	특징	시간 복잡도	공간 복잡도
완전탐색 (DFS)	느리지만 개념 파악에 좋음	O(2^m)	O(m)
메모이제이션	재귀 + 캐시로 중복 제거	O(n×m)	O(n×m)
바텀업 DP	전형적인 표 방식	O(n×m)	O(n×m)
메모리 최적화 DP	공간을 줄인 버전	O(n×m)	O(m)