== 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 P1, P2, ..., Pn, W1, W2,..., Wn and M.
Find X1, X2, ..., Xn, 0 ≤ Xi such that
∑PiXi (1 ≤ i ≤ n) is maximized subject to ∑WiXi ≤ 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(n2)으로 풀립니다. 그러나 우리는 이보다 점근적으로 더 빠른 휴리스틱 버전을 작성해야 합니다.
다음과 같이 input 이 들어온다고 가정합시다. 여기서 맨 앞 하나의 정수는 노드의 수를 나타냅니다. 그 밑으로 노드에 대한 정보가 입력됩니다. 노드의 처음은 key 값이고, 그 다음 값은 확률(확률은 1이상의 정수로 임의로 입력) 입니다. 하나의 노드를 검색했을때 실패하는 경우는 없다고 가정합시다. 최적의 평균탐색시간을 가지는 이진탐색트리를 구현하고 다음을 출력하시오.
Inorder 순회를 통해 각 키값을 모두 출력하고, 또한 각 키값의 탐색시간의 합계를 출력하시오.
!! 주의 : 최적을 구하는 것이 아니고, 빠른 시간안에 최적에 가까운 값을 구하는 것이 목적임.
샘플 Output 에서는 beta를 root 값으로 본 것임. 여러 풀이가 나올 수 있음. 이 페이지의 하위 페이지에 코드와 설명을 올려주세요.
===== input =====
{{| 3
alph 3 beta 7 theta 10 |}}
===== output =====
{{| alph beta theta
33 |}}
===== test =====
|| [알고리즘8주숙제/test] ||
===== 풀이 =====
|| 작성자 || 개발시간 || 풀이 ||
|| [Leonardong] || 2h || [http://wiki.zeropage.org/trac/leonardong/browser/AlgorithmTrainning/OptimalBST.py] ||
|| 김상섭 || 엄청 || [AproximateBinaryTree/김상섭] ||
|| 문보창 || 상섭이형보다많이 || [알고리즘8주숙제/문보창] ||
----