New answers tagged greedy-algorithms
0
Desicion of Algorithms : $ T_{1},T_{2},....,T_{i}$ , cost $ C = C_{1},C_2,....,C_i$
$ \frac{Algo}{Opt} = \frac{C_1 + C_2 + ... + C_i}{(C_1/n_1)*n}$
and $ 4C_1 \geq C_k ,\forall 1 \leq k \leq m$
$ \implies \frac{C_1 + C_2 + ... + C_i}{(C_1/n_1) * n} \leq \frac{4iC_1}{(C_1/n_1)*n} = \frac{4in_1}{n}$
consider $ \frac{C_1}{n_1} \leq \frac{C_k}{n_k} \leq \frac{...
4
In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.
It is obviously that you can swap the order of two consecutive tasks without affecting any other task. In an optimal solution, swapping the order of two consecutive tasks cannot ...
1
Generally speaking, we have a few standard paradigms for designing algorithms: divide-and-conquer, dynamic programming, greedy algorithms, and reduction to an existing known problem. When you have no idea how to solve a problem, one useful strategy is to try each of those paradigms in turn for a little while: spend a little time looking for a divide-and-...
1
To write the profit as a mathematical expression, you need to set up a little more notation for the buys and sells. Let $x[1], \ldots, x[n]$ be the stock prices on days $1, \ldots, n$. For each buy and sell, let $b$ denote the day on which the stock is bought, and $s$ the day on which it is sold. The problem says that we must have $1 \leq b < s \leq n$. ...
Top 50 recent answers are included
