Greedy ¶
1. Friendly Coins ¶
Given the denominations of coins for a newly founded country, the Dairy Republic, and some monetary amount, find the smallest set of coins that sums to that amount. The Dairy Republic is guaranteed to have a 1 cent coin.
2. 0/1 knapsack ¶
Give a greedy method, which is heuristic, to solve the 0/1 knapsack problem and also give an example to show that it does not always yield an optimal solution.
3. kanpsack ¶
The kanpsack problem is defined as follows:
Given positive integers P<sub>1</sub>, P<sub>2</sub>, ..., P<sub>n</sub>, W<sub>1</sub>, W<sub>2</sub>,..., W<sub>n</sub> and M.
Find X<sub>1</sub>, X<sub>2</sub>, ..., X<sub>n</sub>, 0 ≤ X<sub>i</sub> such that
∑P<sub>i</sub>X<sub>i</sub> (1 ≤ i ≤ n) is maximized subject to ∑W<sub>i</sub>X<sub>i</sub> ≤ M (1 ≤ i ≤ n) .
Give a greedy method to find an optimal solution of the knapsack problem and prove its correctness.
Given positive integers P<sub>1</sub>, P<sub>2</sub>, ..., P<sub>n</sub>, W<sub>1</sub>, W<sub>2</sub>,..., W<sub>n</sub> and M.
Find X<sub>1</sub>, X<sub>2</sub>, ..., X<sub>n</sub>, 0 ≤ X<sub>i</sub> such that
∑P<sub>i</sub>X<sub>i</sub> (1 ≤ i ≤ n) is maximized subject to ∑W<sub>i</sub>X<sub>i</sub> ≤ M (1 ≤ i ≤ n) .
Give a greedy method to find an optimal solution of the knapsack problem and prove its correctness.
4. Job Scheduling ¶
Consider the problem of scheduling n jobs on one machine. Describe an algorithm to find a schedule such that its average completion time is minimum. Prove the correctness of your algorithm.
5. Optimal Binary Tree ¶
Optimal Binary Tree Dynamic Programming 한 . 형 하 O(n<sup>2</sup>) . 휴 해 합.
input 합. 하 . 한 . key , 확(확 1 ) . 하 했 패하 합. 평탐 탐트 하 하.
Inorder 회 통해 키 하, 한 키 탐 합 하.
!! : 하 , 하 .
플 Output beta root . . 페 하 페 .
input 합. 하 . 한 . key , 확(확 1 ) . 하 했 패하 합. 평탐 탐트 하 하.
Inorder 회 통해 키 하, 한 키 탐 합 하.
!! : 하 , 하 .
플 Output beta root . . 페 하 페 .
input ¶
{{| 3
alph 3 beta 7 theta 10 |}}
alph 3 beta 7 theta 10 |}}
output ¶
{{| alph beta theta
33 |}}
33 |}}
