Lv.3dpknapsack
가방에 담을 물건 고르기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
물건 n개가 있고, i번 물건의 무게는 weights[i], 가치는 values[i]입니다. 무게를 capacity까지 견디는 가방에 물건을 담으려고 합니다.
각 물건은 통째로 담거나 담지 않거나 둘 중 하나이고, 같은 물건을 두 번 담을 수 없습니다.
담은 물건의 무게 합이 capacity 이하일 때, 가치 합의 최댓값을 반환하세요.
입출력 예
| weights | values | capacity | result |
|---|---|---|---|
[6, 4, 3, 5] | [13, 8, 6, 12] | 7 | 14 |
[10] | [5] | 9 | 0 |
[1, 2, 3] | [10, 15, 40] | 6 | 65 |
입출력 예 설명
예 1 — 무게 4와 3(가치 8 + 6)을 담으면 14입니다. 무게 6짜리(13) 하나보다 낫습니다.
예 2 — 하나뿐인 물건이 너무 무겁습니다.
예 3 — 세 개를 모두 담아도 무게가 6입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(weights: int[], values: int[], capacity: int) → long
제한 사항
-
weights.lengthvalues.length -
weights[i],values[i] -
capacity - 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N * W)
- 공간
- O(W)
입출력 예
| weights | values | capacity | 기대 출력 |
|---|---|---|---|
[6,4,3,5] | [13,8,6,12] | 7 | 14 |
[10] | [5] | 9 | 0 |
[1,2,3] | [10,15,40] | 6 | 65 |
힌트
힌트
best[w] = "지금까지 본 물건들로 무게 합 w 이하를 만들 때 가치의 최댓값"을 무게별로 관리하세요.
물건 (wt, val)을 하나 추가할 때는 best[w] = max(best[w], best[w - wt] + val)입니다.
이때 w를 큰 쪽에서 작은 쪽으로 갱신해야 합니다. 작은 쪽부터 하면 방금 갱신한 값(= 이 물건을 이미 담은 상태)을 다시 써서 같은 물건을 여러 번 담게 됩니다.
가치는 64비트 정수로 더하세요.
복잡도 목표
가지 조합을 모두 시도하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 무게 기준 DP는 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 8 | 판정만 |
| performance | 60 | 4 | 판정만 |