Algorithm Designex07m1_knapsack
0/1 Knapsac with Real Number
07df0cde-2378-4a92-acad-94c3d4e72c55.cppC++
1// Loading code...Selected Submission
100 / 100
0.001s
1604 KB
GreedyBacktrack
Time Comp.
O(2^n) in the worst case, but significantly reduced by the bounding function. The sorting step is O(n log n).
Space Comp.
O(n) due to the recursion depth and the `items` vector.
Readability
6/10
"The code implements a fractional knapsack problem using a recursive approach with bounding to improve efficiency. The core idea is to explore including or excluding each item, and the `upperBound` function provides a heuristic to prune the search space, making it a form of backtracking with optimization."
History
| Attempt | Points | Time ↓ |
|---|---|---|
| Try #24 | 100 | 4/13/2025 |
| Try #23 | 100 | 4/13/2025 |
| Try #22 | 100 | 4/13/2025 |
| Try #21 | 100 | 4/13/2025 |
| Try #20 | 100 | 4/13/2025 |
| Try #19 | 100 | 4/13/2025 |
| Try #18 | 100 | 4/13/2025 |
| Try #17 | 60 | 4/13/2025 |
| Try #16 | 100 | 4/13/2025 |
| Try #15 | 50 | 4/13/2025 |
| Try #14 | 100 | 4/13/2025 |
| Try #13 | 100 | 4/13/2025 |
| Try #12 | 100 | 4/13/2025 |
| Try #11 | 100 | 4/13/2025 |
| Try #10 | 100 | 4/13/2025 |
| Try #9 | 100 | 4/13/2025 |
| Try #8 | 100 | 4/13/2025 |
| Try #7 | 100 | 4/13/2025 |
| Try #6 | 100 | 4/13/2025 |
| Try #5 | 100 | 4/13/2025 |
| Try #4 | 100 | 4/13/2025 |
| Try #3 | 100 | 4/13/2025 |
| Try #2 | 20 | 4/13/2025 |
| Try #1 | 0 | 4/13/2025 |