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