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