Funcia
Lv.3dpknapsack

0/1 Knapsack

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Item i has weight weights[i] and value values[i]. Each item is either taken whole or not at all. Return the maximum total value whose total weight is at most capacity.

Examples

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

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

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

Constraints

  • 1≤n≤1001 \le n \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
  • The answer can exceed 32 bits.

Expected complexity

Time
O(N * W)
Space
O(W)

Examples

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

Hint

Hint

best[w] = max(best[w], best[w - wt] + val) for each item, iterating w downward so an item is used at most once; 64-bit values. Trying all 2n2^n subsets exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.