2
Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.
To answer your question, let's look at a simple example, change-making problem:
Given a set of integer values of coins $C = \{c_1, …, ...
1
Suppose there are $c$ types of balls, and there are $n_i$ balls of type $i$. Let $S$ be a set of types of balls. In how many ways can we choose balls so that only balls of type $S$ appear, and at least one ball of type $i$ appears for each $i \in S$? The answer is clearly
$$ \prod_{i \in S} (2^{n_i} - 1). $$
Taking $S = \{1,\ldots,c\}$, we get a solution to ...
1
Usually, in the context of dynamic programming and optimization methods, we are interested in problems where we have to "find" some value which maximizes \ minimizes a certain function.
For example, take the following problem: You are a cashier in a shop, and a customer gave you an $n$-dollar bill (your country has bills of all kinds! very ...
1
Even though there is a backstory on the naming, as stated in the other answers, the term dynamic programming makes total sense. Dynamic means that something is changing. Programming means keeping a table (program or schedule), as it is implied to the term linear programming, too.
Quoting CLRS
“Programming” in this context refers to a tabular method, not to ...
Only top voted, non community-wiki answers of a minimum length are eligible
