Programación DinámicaIntermediate
Problema de la Mochila 0/1
Problema clásico de programación dinámica donde debes seleccionar elementos con pesos y valores dados para maximizar el valor total mientras te mantienes dentro de una capacidad de peso. Cada elemento solo se puede tomar una vez (0/1). Las aplicaciones incluyen asignación de recursos, optimización de cartera y carga de mercancías.
#dynamic-programming#optimization#combinatorial#np-complete
Complexity Analysis
Time (Average)
O(n × W)Expected case performance
Space
O(n × W)Memory requirements
Time (Best)
O(n × W)Best case performance
Time (Worst)
O(n × W)Worst case performance
📚 CLRS Reference
Introduction to Algorithms•Chapter 16•Section 16.2
How it works
- • 0/1 Knapsack: maximize value within capacity limit
- • Dynamic programming approach
- • O(n × W) time, O(n × W) space complexity
- • Each item can be taken once or not at all
- • Formula: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation