보통DP

0-1 배낭

각 원소가 [무게, 가치]인 물건 배열 items와 배낭이 버틸 수 있는 무게 한도 capacity가 주어져요. 물건은 쪼갤 수 없고, 각 물건은 넣거나 안 넣거나 둘 중 하나예요(그래서 0-1 배낭이에요).

무게 합이 capacity를 넘지 않게 골랐을 때 가치 합의 최댓값을 반환해요.

용량을 상태 축으로 둬요. dp[c]를 '한도가 c일 때의 최대 가치'라 하고, 물건을 하나씩 보며 dp[c] = max(dp[c], dp[c - 무게] + 가치)로 갱신해요. 한 물건을 두 번 쓰지 않도록 용량은 큰 쪽부터 훑어요.

예시

예시 1

입력: items = [[6, 13], [4, 8], [3, 6], [5, 12]], capacity = 10
출력: 21
설명: 무게 6·4짜리(가치 13·8)를 담으면 무게 합 10, 가치 합 21로 최대예요.

예시 2

입력: items = [[1, 1], [3, 4], [4, 5], [5, 7]], capacity = 7
출력: 9
설명: 무게 3·4(가치 4·5)를 담아 무게 7, 가치 9예요.

제한 사항

1 ≤ items.length ≤ 100
1 ≤ 무게 ≤ capacity ≤ 10,000
1 ≤ 가치 ≤ 1,000

dp를 capacity + 1 크기로 0으로 채워요. 각 물건 [w, v]마다 용량 c를 capacity에서 w까지 거꾸로 내려가며 dp[c] = Math.max(dp[c], dp[c - w] + v)로 갱신해요. 거꾸로 도는 게 같은 물건을 두 번 담지 않게 하는 핵심이에요.

javascript
Copy code
function knapsack(items, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (const [weight, value] of items) {
    for (let c = capacity; c >= weight; c--) {
      dp[c] = Math.max(dp[c], dp[c - weight] + value);
    }
  }
  return dp[capacity];
}

이전 문제격자 경로의 수

다음 문제최장 공통 부분 수열

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.