E D R , A S I H C RSS

알고리즘8주숙제

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.

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
{{| 3
alph 3 beta 7 theta 10 |}}
output
{{| alph beta theta
33 |}}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1003 sec