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.

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.

The kanpsack problem is defined as follows:
Given positive integers P₁, P₂, ..., P_n, W₁, W₂,..., W_n and M.
Find X₁, X₂, ..., X_n, 0 ≤ X_i such that
∑P_iX_i (1 ≤ i ≤ n) is maximized subject to ∑W_iX_i ≤ M (1 ≤ i ≤ n) .
Give a greedy method to find an optimal solution of the knapsack problem and prove its correctness.

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.

Optimal Binary Tree는 Dynamic Programming 기법으로 풀리는 유명한 문제입니다. 그누스 형님 방법에 의하면 O(n²)으로 풀립니다. 그러나 우리는 이보다 점근적으로 더 빠른 휴리스틱 버전을 작성해야 합니다.
다음과 같이 input 이 들어온다고 가정합시다. 여기서 맨 앞 하나의 정수는 노드의 수를 나타냅니다. 그 밑으로 노드에 대한 정보가 입력됩니다. 노드의 처음은 key 값이고, 그 다음 값은 확률(확률은 1이상의 정수로 임의로 입력) 입니다. 하나의 노드를 검색했을때 실패하는 경우는 없다고 가정합시다. 최적의 평균탐색시간을 가지는 이진탐색트리를 구현하고 다음을 출력하시오.
Inorder 순회를 통해 각 키값을 모두 출력하고, 또한 각 키값의 탐색시간의 합계를 출력하시오.
!! 주의 : 최적을 구하는 것이 아니고, 빠른 시간안에 최적에 가까운 값을 구하는 것이 목적임.
샘플 Output 에서는 beta를 root 값으로 본 것임. 여러 풀이가 나올 수 있음. 이 페이지의 하위 페이지에 코드와 설명을 올려주세요.

{{| 3
alph 3 beta 7 theta 10 |}}

{{| alph beta theta
33 |}}

알고리즘8주숙제/test

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