Allen Career Institute: Algorithm

Question

Identify the algorithm which works on the principle that locally optimal solutions are globally optimal.

$\left ( A \right )$ Divide and Conquer

$\left ( B \right )$ Greedy

$\left ( C \right )$ Dynamic Programming

$\left ( D \right )$ All of the above

Comments

@srestha

> why Fractional Knapsack cannot be solved with D.P. ?

- Can you please provide source of the statement fractional knapsack cannot be solved with DP.?

I think if we were to solve fractional knapsack by using DP, we would need to take the maximum of all combinations of items' prices and weights. It will just be super inefficient even if the problems do overlap, and we'll eventually get the correct answer assuming the "fractions" of the items will be finite assuming we're not allowed to split atoms into protons and electrons and so on. 

Correct me if I'm wrong. 

---

Can you please provide source of the statement fractional knapsack cannot be solved with DP.?

cormen :) 

---

@srestha page no. ? 

I think there's a difference between unsolvable and solvable but not suitable. Unsolvable means, the algorithm will either give false results, or it will not give expected results at all. 

I think CLRS says it will not be a good idea to use DP for fractional knapsack, cause the no. of subproblems will be HUGE, and no. of overlapping problems will be much less. Luckily, fractional knapsack exhibits greedy choice property, which drastically reduces no. of subproblems, and hence the complexity. Correct me if I'm wrong?

@ankitgupta.1729 

> How to know if a problem has greedy choice property?

- Depends on the problem I think. Intuition maybe? That's why coming up with a greedy algorithm and giving proof of correctness for a problem is much difficult, and there's no mechanical method for it. 

> why locally optimally choice of maximum profit or minimum weight does not give globally optimal solution of this problem?

- CLRS for life.