Funcia
Lv.3dpknapsack

가방에 담을 물건 고르기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

물건 n개가 있고, i번 물건의 무게는 weights[i], 가치는 values[i]입니다. 무게를 capacity까지 견디는 가방에 물건을 담으려고 합니다.

각 물건은 통째로 담거나 담지 않거나 둘 중 하나이고, 같은 물건을 두 번 담을 수 없습니다. 담은 물건의 무게 합이 capacity 이하일 때, 가치 합의 최댓값을 반환하세요.

입출력 예

weightsvaluescapacityresult
[6, 4, 3, 5][13, 8, 6, 12]714
[10][5]90
[1, 2, 3][10, 15, 40]665

입출력 예 설명

예 1 — 무게 4와 3(가치 8 + 6)을 담으면 14입니다. 무게 6짜리(13) 하나보다 낫습니다.

예 2 — 하나뿐인 물건이 너무 무겁습니다.

예 3 — 세 개를 모두 담아도 무게가 6입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(weights: int[], values: int[], capacity: int) → long

제한 사항

  • 1≤n=1 \le n = weights.length == values.length ≤100\le 100
  • 1≤1 \le weights[i] ≤50,000\le 50{,}000, 1≤1 \le values[i] ≤109\le 10^9
  • 1≤1 \le capacity ≤50,000\le 50{,}000
  • 답은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O(N * W)
공간
O(W)

입출력 예

weightsvaluescapacity기대 출력
[6,4,3,5][13,8,6,12]714
[10][5]90
[1,2,3][10,15,40]665

힌트

힌트

best[w] = "지금까지 본 물건들로 무게 합 w 이하를 만들 때 가치의 최댓값"을 무게별로 관리하세요.

물건 (wt, val)을 하나 추가할 때는 best[w] = max(best[w], best[w - wt] + val)입니다. 이때 w를 큰 쪽에서 작은 쪽으로 갱신해야 합니다. 작은 쪽부터 하면 방금 갱신한 값(= 이 물건을 이미 담은 상태)을 다시 써서 같은 물건을 여러 번 담게 됩니다.

가치는 64비트 정수로 더하세요.

복잡도 목표

2n2^n가지 조합을 모두 시도하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 무게 기준 DP는 O(n⋅capacity)O(n \cdot \text{capacity})입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness408판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.