Dodomeki
Sign in

113. 0/1 Knapsack

Hard

A knapsack has a maximum weight of capacidade. For each item i, pesos[i] and valores[i] give its weight and value. Return the maximum value that fits in the knapsack, using each item at most once.

Example 1
Input: pesos = [2, 3, 4], valores = [4, 5, 7], capacidade = 5
Output: 9
Explanation: The items with weights 2 and 3 add up to value 9.
Example 2
Input: pesos = [1, 3, 4], valores = [2, 6, 7], capacidade = 4
Output: 8
Constraints
  • 0 <= pesos.length = valores.length <= 200
  • 1 <= pesos[i] <= 1000
  • 0 <= valores[i] <= 10^6
  • 0 <= capacidade <= 10^4
Dynamic programmingArrays
Caso 1
pesos =
[2,3,4]
valores =
[4,5,7]
capacidade =
5
Expected =
9
Caso 2
pesos =
[1,3,4]
valores =
[2,6,7]
capacidade =
4
Expected =
8

Run checks these 2 cases. Submit runs all 6, including hidden ones.