People who code: we want your input. Take the Survey

# Tag Info

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 ...