[DP] 0/1 Knapsack 문제: 최대 profit 가지는 가방 선택 문제 ★★★

0/1 Knaptsack: 가방 넣거나 빼거나. 문제

• weight[i] 를 참고해서 capacity 용량(== sum(weight[i])을 만족하면서.
• profit 최대화(<= sum(profit[i]) 되게, 0 빼거나, 1 넣거나 ex1)

 

profit = [4,4,7,1] 이고 weight = [5,2,3,1], capacity = 8 일때 최대 profit 은?

capacity 가 8 로 시작해서

i=0, weight[0] = 5 선택O 하거나 => 남는 capacity C = 3 또는

      -> i=1 선택 O 하거나 => 남는 C=1

          -> i=2 선택 O 하거나 => 남는 C=-2 => 선택 못함

              -> i=3 진행X

          -> i=2 선택 X 하거나 => 남는 C=1

              -> i=3 선택 O 하거나 => 남는 C=0

              -> i=3 선택 X 하거나 => 남는 C=1

       -> i=1 선택 X 하거나 => 남는 C=3

           -> i=2 선택 O 하거나 => 남는 C=0

               -> i=3 진행X

           -> i=2 선택 X 하거나 => 남는 C=3

i=0, weight[0] = 5 선택X 하거나 => 남는 capacity C = 8

       -> i=1 선택 O 하거나 => 남는 C=6

           -> i=2 선택 O 하거나 => 남는 C=3

           -> i=2 선택 X 하거나 => 남는 C=6

       -> i=1 선택 X 하거나 => 남는 C=8

           -> i=2 선택 O 하거나 => 남는 C=5

           -> i=2 선택 X 하거나 => 남는 C=8

 

이렇게 계속 아이템 넣거나 빼거나..

그래서 이진트리 BST 로.. 트리 사이즈(=깊이): n 개=> 2^n

---

 

0/1 Knapsack 문제의 핵심 개념을 정확히 잘 파악하고 있고,
**"각 아이템에 대해 넣을지/말지를 결정하는 이진 트리 구조"**로 설명한 것도 정말 훌륭합니다.

---

✅ 핵심 요약

"각 아이템은 선택하거나(1) 또는 선택하지 않거나(0)"
→ ✅ 맞습니다. 이것이 0/1 배낭 문제의 기본 전제입니다.

"capacity(가방 용량) 제한 안에서 profit 최대화"
→ ✅ 맞습니다. 최대 profit을 얻는 것이 목표입니다.

"각 단계마다 아이템을 넣거나 빼거나를 선택하며, 이진 트리로 볼 수 있다"
→ ✅ 맞습니다. 각 아이템에 대해 "넣는다 / 안 넣는다" 선택 → 전체 탐색 공간은 2^n개의 경우의 수

예시를 트리 형태로 branching 시뮬레이션한 것도 정확합니다.

---

🎯 예시 복습:

profit = [4, 4, 7, 1], weight = [5, 2, 3, 1], capacity = 8

이 문제의 해답을 구하는 방식은 다음과 같아요:

DFS (백트래킹) 트리 구조 예시

• 루트부터 시작해서 각 아이템을 넣거나 말거나 분기
• 현재까지 누적 weight가 capacity를 넘지 않도록
• 마지막까지 갔을 때 최대 profit을 갱신

---

✅ 최적해 구하기 (정답)

우리가 가능한 조합 중 총 weight ≤ 8이면서 profit이 최대인 조합을 찾으면 됩니다:

• [1, 2] 선택 (weight=2+3=5, profit=4+7=11)
• [1, 3, 2] 선택 (weight=2+1+3=6, profit=4+1+7=12)
• [2, 1, 3] 선택 (같음)

✔️ 최대 profit = 12

---

🧠 최적화 전략

✅ DFS (재귀 + 백트래킹)

def knapsack(i, capacity):
    if i == len(weight):
        return 0
    if weight[i] > capacity:
        return knapsack(i + 1, capacity)  # 현재 아이템 못 담음
    return max(
        knapsack(i + 1, capacity),  # 담지 않음
        profit[i] + knapsack(i + 1, capacity - weight[i])  # 담음
    )

 

또는

# Given a list of N items, and a backpack with a
# limited capacity, return the maximum total profit that 
# can be contained in the backpack. The i-th item's profit
# is profit[i] and it's weight is weight[i]. Assume you can
# only add each item to the bag at most one time. 

# Brute force Solution
# Time: O(2^n), Space: O(n)
# Where n is the number of items.
def dfs(profit, weight, capacity):
    return dfsHelper(0, profit, weight, capacity)

def dfsHelper(i, profit, weight, capacity):
    if i == len(profit):
        return 0

    # Skip item i
    maxProfit = dfsHelper(i + 1, profit, weight, capacity)

    # Include item i
    newCap = capacity - weight[i]
    if newCap >= 0:
        p = profit[i] + dfsHelper(i + 1, profit, weight, newCap)
        # Compute the max
        maxProfit = max(maxProfit, p)

    return maxProfit

✅ 메모이제이션(캐슁)

# Memoization Solution
# Time: O(n * m), Space: O(n * m)
# Where n is the number of items & m is the capacity.
def memoization(profit, weight, capacity):
    # A 2d array, with N rows and M + 1 columns, init with -1's
    N, M = len(profit), capacity
    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]

    # Skip item i
    cache[i][capacity] = memoHelper(i + 1, profit, weight, capacity, cache)
    
    # Include item i
    newCap = capacity - weight[i]
    if newCap >= 0:
        p = profit[i] + memoHelper(i + 1, profit, weight, newCap, cache)
        # Compute the max
        cache[i][capacity] = max(cache[i][capacity], p)

    return cache[i][capacity]

 

✅ 2D DP를 사용한 0/1 Knapsack 문제의 Bottom-Up 방식

# dp[i][c]: i번째 아이템부터 시작해서, 현재 용량이 c일 때 얻을 수 있는 최대 이익
# n+1 행: 아이템 인덱스 0~n (n은 사용 안함, base case 용)
# capacity+1 열: 가방 용량 0~capacity
dp = [[0] * (capacity + 1) for _ in range(n + 1)]

# 아이템 인덱스를 n-1부터 0까지 거꾸로 순회 (Bottom-up 방식)
for i in range(n - 1, -1, -1):
    # 용량 c를 0부터 capacity까지 순회
    for c in range(capacity + 1):
        if weight[i] > c:
            # 현재 아이템을 넣을 수 없는 경우 (무게가 초과됨)
            # → 그냥 이전 결과 그대로 사용 (i+1번째부터 시작한 값)
            dp[i][c] = dp[i + 1][c]
        else:
            # 현재 아이템을 넣을 수 있는 경우
            # 1. i번째 아이템을 **넣지 않은 경우**: dp[i + 1][c]
            # 2. i번째 아이템을 **넣은 경우**: profit[i] + dp[i + 1][c - weight[i]]
            # 두 경우 중 최대값을 선택
            dp[i][c] = max(
                dp[i + 1][c],                          # 아이템을 선택하지 않음
                profit[i] + dp[i + 1][c - weight[i]]  # 아이템을 선택함
            )
            
# dp[0][capacity]: 0번째 아이템부터 시작해서, capacity만큼 쓸 수 있을 때의 최대 profit
return dp[0][capacity]

🔍 예시로 생각하면:

• dp[2][5]: 2번째 아이템부터 시작해서 용량 5일 때 가능한 최대 profit
• 각 셀은 이전 계산을 기반으로 채워지고, 마지막에는 dp[0][capacity]에 정답이 위치함

✅ DP 

# Dynamic Programming Solution
# Time: O(n * m), Space: O(n * m)
# Where n is the number of items & m is the capacity.
def dp(profit, weight, capacity):
    N, M = len(profit), capacity
    dp = [[0] * (M + 1) for _ in range(N)]

    # Fill the first column and row to reduce edge cases
    for i in range(N):
        dp[i][0] = 0
    for c in range(M + 1):
        if weight[0] <= c:
            dp[0][c] = 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-1][c - weight[i]]
            dp[i][c] = max(include, skip)
    return dp[N-1][M]

✅ DP 메모리 최적

# Memory optimized Dynamic Programming Solution
# Time Complexity: O(n * m) => n: 아이템 개수, m: 최대 가방 용량
# Space Complexity: O(m) => 현재/이전 row만 사용하여 공간 최적화
def optimizedDp(profit, weight, capacity):
    N, M = len(profit), capacity  # N: 아이템 수, M: 가방 최대 용량
    dp = [0] * (M + 1)            # dp[c]: 현재까지 고려한 아이템으로 용량 c일 때 최대 profit 저장

    # 첫 번째 아이템에 대해 처리
    # weight[0] 이하인 용량에 대해서는 profit[0]을 담을 수 있음
    for c in range(M + 1):
        if weight[0] <= c:
            dp[c] = profit[0]     # 첫 아이템이 들어갈 수 있는 경우 초기값 세팅

    # 나머지 아이템들에 대해 DP 반복
    for i in range(1, N):
        curRow = [0] * (M + 1)    # 현재 아이템(i)에 대해 새로 계산할 행
        for c in range(1, M + 1):  # 용량 1부터 M까지 검사
            skip = dp[c]          # 현재 아이템을 선택하지 않는 경우 (이전 결과 그대로)
            include = 0
            if c - weight[i] >= 0:  # 현재 아이템을 담을 수 있을 때
                include = profit[i] + dp[c - weight[i]]  # 현재 아이템을 담았을 때의 profit 계산
            curRow[c] = max(include, skip)  # 담거나 말거나 중 profit이 큰 쪽 선택
        dp = curRow  # 다음 루프에서 현재 row를 기준으로 갱신

    return dp[M]  # 최대 용량일 때 최대 profit 반환

✅ 핵심 요약

• dp[c]: 용량이 c일 때 최대 이익 (이전 아이템 기준)
• curRow[c]: 현재 아이템 포함 여부를 고려한 새로운 결과
• 공간 복잡도 O(n*m) → O(m)으로 줄이기 위해 2D → 1D 배열 전환
• dp = curRow: 현재 계산된 결과를 다음 루프에서 기준으로 사용

---

🔚 결론

• 당신이 설명한 "이진 트리 구조로 모든 선택지를 따라간다"는 개념은 정확합니다!
• 전체 탐색은 2^n이지만, 메모이제이션(DP) 을 쓰면 O(n * capacity)로 줄일 수 있어요.
• DFS → DP → Bottom-up 순으로 최적화 단계를 밟으면 좋습니다.

class Solution:
    def maximumProfit(self, profit: List[int], weight: List[int], capacity: int) -> int:
        N = len(profit)
        dp = [[0] * (capacity+1) for _ in range(N+1)]

        for i in range(N-1, -1, -1): # from n-1 to 0
            for c in range(capacity+1): # from 0 to capacity
                if weight[i] > c: # 현재 용량을 무게가 초과하면, 못넣음, 이전 결과 사용
                    dp[i][c] = dp[i+1][c]
                else: # 현재 용량을 수용할수 있으면, 현재 아이템 추가O 또는 현재 아이템 추가X 중 최대값 업데이트
                    # i 번째 현재 아이템 추가X 은 이익: dp[i+1][c]
                    # 지금 선택한 i 번째 아이템의 이익: profit[i]
                    # c-weight[i]: 아이템 넘고 남은 가방 용량
                    # 남은 용량에서 다음 아이템[i+1]로 부터 얻을수 있는 최대 이익
                    # i 번째 현재 아이템 추가O 은 이익: profit[i] + dp[i+1][c-weight[i]]                    
                    dp[i][c] = max(profit[i] + dp[i+1][c-weight[i]], dp[i+1][c])
        return dp[0][capacity]

i+1 이긴 하지만, 이전 결과..로 이해!! 필요..

이전 결과는 다음 아이템 사용해서 먼저 결과 도출하였음

 

위 아래 코드.. 동일..

n = len(profit)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]  # 0~n까지 총 n+1행

for i in range(1, n + 1):  # 정순
    for c in range(capacity + 1):
        if weight[i - 1] > c:
            dp[i][c] = dp[i - 1][c]  # 현재 아이템을 담지 못함
        else:
            dp[i][c] = max(
                dp[i - 1][c],  # 담지 않음
                profit[i - 1] + dp[i - 1][c - weight[i - 1]]  # 담음
            )
return dp[n][capacity]