目录
- 活动选择问题
- 贪心算法的原理
- 01背包和分数背包
- 赫夫曼编码
If you can’t win the game, remember what you play game is to make yourself happy. So whatever win or lose you should be happy.
贪心算法的核心就是每次都选择局部最优解，然后将这些解拼起来，这样做可以得到一个比较好的解，但是不一定是最优解。
活动选择问题
有一批活动，但是举办活动的位置只有一个地方，我们希望在一定的时间内举行尽可能多的活动。
S = {a1,a2,a3 … an},对应的si和fi为第i个活动的开始和结束时间，si为闭，fi为开。
我们把活动结束时间从小到大排序：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| si | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| fi | 4 | 5 | 6 | 7 | 9 | 9 | 10 | 11 | 12 | 14 | 16 |
寻找最优解，Sij表示在ai活动结束之后，aj活动开始之前的活动集合，我们假设Aij就是这样的一个子集，包含活动ak，最后就有Aij = Aik+ak+Akj。
递归式： c[i,j] = c[i,k] + c[k,j] + 1.
接下来可以通过动态递归算法来求解。
使用贪心算法的时候就直接考虑最先结束的，这样留给其它活动的时间就会多。每次都选择在剩余的时间内最先结束的。
1
2
3
4
5
6
7
8
9
10
local s = { 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 }
local f = { 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16 }
local result = {}
local endTime = -1
for i = 1, #f do
if s[i] >= endTime then
table.insert(result, i)
endTime = f[i]
end
end
这里也可以=考虑使用动态规划，利用递归来求得最优解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
local s = { 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 }
local f = { 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16 }
local result = {}
local mem = {}
local findActs = function(i, j)
local acts = {}
for k = i + 1, j - 1 do
if (not f[i] or s[k] >= f[i]) and (not s[j] or f[k] <= s[j]) then
table.insert(acts, k)
end
end
return acts
end
local Optimal
Optimal = function(i, j)
if i >= j then
return 0
end
local ks = findActs(i, j)
local max = 0
local k = 0
local a1, a2
if #ks == 0 then
a1 = mem[(i + 1) .. j] or Optimal(i + 1, j)
a2 = mem[i .. (j - 1)] or Optimal(i, j - 1)
max = math.max(a1, a2)
mem[i .. j] = max
else
for m, v in ipairs(ks) do
a1 = mem[i .. v] or Optimal(i, v)
a2 = mem[v .. j] or Optimal(v, j)
local container = 1 + a1 + a2
if container > max then
max = container
k = v
end
end
mem[i .. j] = max
table.insert(result, k)
end
return max
end
local max = Optimal(0, 12)
贪心算法原理
贪心算法通过做出一系列的选择来求出问题的最优解。在每个决策定，它做出在当时看来最佳的选择。这种启发式策略并不能抱枕总是能找到最优解。
- 确定问题的最优子结构
- 设定一个递归算法
- 证明如果我们做出一个贪心选择，只剩下一个子问题
- 证明贪心选择总是安全的
- 设计一个递归算法实现贪心策略
- 将递归算法转换为迭代算法。
我们可以按照如下的步骤这几贪心算法：
- 将最优问题转换为这样的形式：对其作出一个选择后，只剩下一个子问题需要求解
- 证明作出贪心选择后，原问题总是存在最优解，即贪心选择是安全的
- 证明贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到最优解，这样就得到最优子结构。
01背包和分数背包
在贪心算法中，01背包就不能使用贪心算法，这是因为限重的那个条件。
分数背包问题就不存在这个问题，因为它可以取这个物品的几分之几，所以永远选择价值最高的那个问题就行了。
在这里我们队01背包问题进行动态归还的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
local goodWeights = { 10, 20, 30 }
local goodsValue = { 60, 100, 120 }
local zeroBag
local result = {}
local mem = {}
zeroBag = function(i, w, value)
if not goodWeights[i] or w == 0 then
return value
end
if mem[i .. w] then
return mem[i .. w]
end
local valueNotGet, valueGet
valueNotGet = zeroBag(i + 1, w, value)
if w > goodWeights[i] then
valueGet = zeroBag(i + 1, w - goodWeights[i], value + goodsValue[i])
if valueNotGet > valueGet then
mem[i .. w] = valueNotGet
else
print(i, w, valueGet)
table.insert(result, i)
mem[i .. w] = valueGet
end
else
mem[i .. w] = valueNotGet
end
return mem[i .. w]
end
zeroBag(1, 50, 0)
分数背包问题可以直接使用贪心算法一直去单位重量价值最高的物品。
赫夫曼编码
赫夫曼编码可以很有效的一所数据：通常可以节省20%-90%的空间，具体压缩率依赖于数据的特特征。我们将待压缩数据看做字符序列。根据每个字符的出现频率，赫夫曼贪心算法构造出字符的最优二进制表示。
我们遍历出所有的字符，并根据其出现的频率进行从大到小的排序，在本节中我们烤炉使用一种二进制字符编码的方法，每个字符用一个唯一的二进制串表示，称为码字。如果使用定长的编码，如果有6为的话需要3位。如果有100 000个字符的话需要300 000个二进制来编码文件。
在这里我们可以使用变长编码：其思想主要是赋予高频字短的编码串，赋予低频字长的编码串。
对于变长编码，我们使用的是前缀码，即没有任何码字是其它码字的前缀。
如何生成这个变长编码，这个变长编码的生成规则就做赫夫曼编码，就是通过构造一颗赫夫曼树，来实现赫夫曼编码。
每次就最小的两个节点作为子节点生成一个新的父节点，然后使用这个父节点作为新的节点再来排序这样循环直到生成一个根节点。这样就可以得到一个赫夫曼树，所有的叶子结点表示一个字符，从根节点到叶子结点的路径就是编码，左孩子路径为0，右孩子路径为1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
node = { 5, 9, 12, 13, 16, 45 }
tree = {}
for i = 1, #node do
local tempTree = {}
tempTree.root = node[i]
tempTree.left = nil
tempTree.right = nil
table.insert(tree, tempTree)
end
local function getTwoMin()
table.sort(tree, function(a, b)
return a.root < b.root
end)
return tree[1], tree[2]
end
local function huffman()
while #tree > 1 do
local tree1, tree2 = getTwoMin()
local newTree = {}
newTree.root = tree1.root + tree2.root
newTree.left = tree1
newTree.right = tree2
table.remove(tree, 1)
table.remove(tree, 1)
table.insert(tree, newTree)
end
end
huffman()
local result = tree[1]
