Algo-Greedy

Activity-Selection problem

pseudocode

Greedy-Activity-Selectors(s,f)
	n = s.length
	A = {a[1]}
	k = 1
	for m = 2 to n
		if s[m] >= f[k]
			A = A ∪ {a[m]}
			k = m
	return A

python

def act_select(s,f):
    n = len(s)
    A = set()
    A.add(1)
    k = 1
    for m in range(2,n):
        if s[m] >= f[k]:
            A.add(m)
            k = m
    return A

if __name__ == '__main__':
    s = [0, 1, 3, 0, 5, 3, 5,  6,  8,  8,  2, 12]
    f = [0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
    print(act_select(s,f))

The Knapsack problem

Fractional Knapsack

pseudocode

Fraction-Knapsack(v,w,W)
	計算v[i]/w[i], ∀i = 1,2,...,n       => O(n)  
	將每件物品根據v[i]/w[i]由大到小排列   => O(nlogn)
	依序取物直到總負重達到W貨或物品全被取光為止

0-1 Knapsack (DP解)

沒有greedy-choice property, 所以無法用greedy, 只能用DP解。
pseudocode

01-knapsack(n,v,w,W)
	Let s[0..n, 0..W] be a new array
	for k = 0 to W
		s[0,k] = 0
	for i = 0 to n 
		s[i,0] = 0
		for k = 1 to W
			if k < w[i]
				s[i,k] = s[i-1,k]
			else
				s[i,k] = max{s[i-1,k], v[i]+s[i-1,k-w[i]]}
	return s[n,W]

Huffman code

pseucode

Huffman(s)
	find least frequence chars c and c'
	S' = remove c and c' from S, but add char X with f[x] = f[c] + d[c']
	T' = Huffman(S')
	make leaf X of T' an interal node by connecting two leaves c and c' to it
	return resulting tree

constructing

Huffman(c)
	n ← |C|
	Q ← C  # initialize the min-priority queue with the character in C
	for i ← 1 to n-1
		do allocate a new node z
			z.left = x = EXTRACT-MIN(Q)
			z.right = y = EXTRACT-MIN(Q)
			z.freq = x.freq + y.freq
			INSERT(Q,z)
	return EXTRACT-MIN(Q) # return the root of the tree