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