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 |}}
test ¶
풀이 ¶
| 작성자 | 개발시간 | 풀이 |
| Leonardong | 2h | http://wiki.zeropage.org/trac/leonardong/browser/AlgorithmTrainning/OptimalBST.py |
| 김상섭 | 엄청 | AproximateBinaryTree/김상섭 |
| 문보창 | 상섭이형보다많이 | 알고리즘8주숙제/문보창 |
