Dynamische ProgrammierungIntermediate
0/1-Rucksackproblem
Klassisches dynamisches Programmierungsproblem, bei dem Sie Gegenstande mit gegebenen Gewichten und Werten auswahlen mussen, um den Gesamtwert zu maximieren und dabei innerhalb einer Gewichtskapazitat zu bleiben. Jeder Gegenstand kann nur einmal genommen werden (0/1). Anwendungen umfassen Ressourcenallokation, Portfoliooptimierung und Frachtbeladung.
#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