New answers tagged dynamic-programming
0
votes
Knapsack problem 0/1 with even number of items
Note: At the time of my writing, the only other answer to this question seems incorrect. I do not agree that $DP_\text{e}(0,j) = -\infty$ for all $j > 0$. Whether the backpack is full ($j = 0$) or ...
0
votes
3 Processor Scheduling
You should be able to do this in exponential time, but much faster than n^3 operations.
Get a quick upper bound by sorting the tasks in descending length, then scheduling each task in turn to the ...
Top 50 recent answers are included
Related Tags
dynamic-programming × 951algorithms × 541
optimization × 108
graphs × 76
greedy-algorithms × 68
knapsack-problems × 61
recursion × 56
time-complexity × 39
combinatorics × 39
algorithm-analysis × 34
data-structures × 33
recurrence-relation × 33
arrays × 28
subsequences × 28
strings × 26
matrices × 26
trees × 24
memoization × 23
shortest-path × 21
complexity-theory × 19
runtime-analysis × 18
correctness-proof × 17
np-complete × 16
scheduling × 16
backtracking × 16