People who code: we want your input. Take the Survey
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