배낭 문제

무게 한도 안에서 가치를 최대로 담아요. `dp[w]`를 뒤에서부터 갱신하면 0/1 배낭이에요.

이럴 때 써요

물건마다 무게와 가치가 있고, 무게 한도 안에서 가치 합을 최대로 만들 때
각 물건을 담거나 안 담거나 둘 중 하나로 골라야 할 때 (0/1)
특정 합을 정확히 만들 수 있는지 묻는 문제 (부분집합 합 subset-sum)
용량·예산 같은 한도가 있고, 그 안에서 최적을 찾는 냄새가 날 때

개념

물건이 n개, 배낭 용량이 W예요. 물건마다 무게 weight와 가치 value가 있고, 각 물건은 한 번만 담을 수 있어요(0/1 배낭). 무게 합이 W를 넘지 않게 하면서 가치 합을 최대로 만드는 게 목표예요.dp[w]를 용량이 w일 때 담을 수 있는 최대 가치로 정의해요. 물건 하나를 볼 때 선택은 둘이에요. 안 담으면 dp[w] 그대로. 담으면 그 물건 무게만큼 비운 자리의 최선에 가치를 더한 dp[w - weight] + value. 둘 중 큰 쪽을 골라요. 그래서 dp[w] = max(dp[w], dp[w - weight] + value).

"물건 (w2,v3),(w3,v4), 용량 5 — dp를 무게 역순으로"
dp 초기값: [0, 0, 0, 0, 0, 0]   (인덱스 0..5)
물건1 (무게2, 가치3): w = 5 → 2 로 내려가며
  w=5: max(0, dp[3]+3) = max(0, 3) = 3
  w=4: max(0, dp[2]+3) = max(0, 3) = 3
  w=3: max(0, dp[1]+3) = max(0, 3) = 3
  w=2: max(0, dp[0]+3) = max(0, 3) = 3
  dp: [0, 0, 3, 3, 3, 3]
물건2 (무게3, 가치4): w = 5 → 3 으로 내려가며
  w=5: max(3, dp[2]+4) = max(3, 7) = 7
  w=4: max(3, dp[1]+4) = max(3, 4) = 4
  w=3: max(3, dp[0]+4) = max(3, 4) = 4
  dp: [0, 0, 3, 3, 4, 7]
답: dp[5] = 7   (두 물건 다 담기: 무게 5, 가치 7)

부분집합 합(subset-sum)도 똑같은 틀이에요. 가치 대신 무게 = 값으로 두고, dp[w]를 true/false로 바꾸면 그 합을 정확히 만들 수 있나?를 풀 수 있어요. 갱신도 dp[w] = dp[w] || dp[w - value] 한 줄이면 돼요.

무게 도는 방향	결과	쓰임
역순 (`W` → `weight`)	물건 한 번만	0/1 배낭
정방향 (`weight` → `W`)	물건 여러 번	무한(완전) 배낭

패턴 코드

0/1 배낭 — 1차원 DP, 무게 역순 갱신물건마다 무게를 capacity부터 weight까지 역순으로 돌아 한 물건이 한 번만 담기게 해요. 답은 dp[capacity]예요.

javascript
Copy code
function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    const weight = weights[i];
    const value = values[i];
    // 무게를 역순으로: 이번 물건을 두 번 담지 않도록
    for (let w = capacity; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[capacity];
}

이 유형으로 풀어보기

← 1차원 DP — 점화식 세우기 동전 교환 — 최소 개수·경우의 수 →