赞
踩
用¥100买书一本, 花去¥29.7, 如何找补零钱, 所用的总张数最少?
某国家的钱分20, 11, 5, 1 cents四种, 如果用20cents买5cents的东西, 需要如何找使得钱的张数最少?
公司不同职员申请使用某一会议室, 他们的活动起止时间如向量
s
s
s 与
f
f
f 所示. 例如, 第 1 个活动预计 1 点至 5 点, 第 2 个活动预计 2 点至 3 点. 如何安排, 使得该会议室可以容纳最大数量的活动?
s
=
[
0
,
1
,
2
,
3
,
3
,
5
,
5
,
6
,
8
,
8
,
12
]
s = [0, 1, 2, 3, 3, 5, 5, 6, 8, 8, 12]
s=[0,1,2,3,3,5,5,6,8,8,12]
f
=
[
6
,
4
,
13
,
5
,
8
,
7
,
9
,
10
,
11
,
12
,
14
]
f = [6, 4, 13, 5, 8, 7, 9, 10, 11, 12, 14]
f=[6,4,13,5,8,7,9,10,11,12,14]
各活动的开始时间和结束时间存储于数组 s s s 和 f f f 中, 且按结束时间的非减序排列
i i i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
s [ i ] s[i] s[i] | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
f [ i ] f[i] f[i] | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
选择第一个活动, 依次跳过后面与其冲突的活动, 再选择第一个与之不冲突的活动, 以此类推.
/** * Title: 活动安排问题.<br> * Version: 1.0<br> * Copyright: Copyright (c) 2003, all rights reserved<br> * Author: 闵帆<br> * Company: <a href=http://www.fansmale.com>www.fansmale.com</a><br> * Written time: 2003/09/02<br> * Last modify time: 2021/11/30<br> */ public class GreedySelector{ /** 入口方法. */ public static void main(String args[]){ int [] startTimes = {-1, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; int [] finishTimes = {-1, 4, 5, 6, 7, 8, 9,10,11, 12,13,14}; boolean [] isSelected = new boolean[12]; int successActivity = greedySelector(startTimes, finishTimes, isSelected); for (int i = 1; i <= 11; i++){ if (isSelected[i]){ System.out.print(startTimes[i] + "->" + finishTimes[i] + "\t"); }//Of if }//Of for System.out.println("\n" + successActivity + " activities are successfully scheduled."); }//Of main /** ********************************* * 获取最优解, 即最多活动数. * @param s 开始时间向量. * @param f 结束时间向量. * @param a 是否安排. ********************************* */ public static int greedySelector(int []s, int []f, boolean a[]){ int n = s.length - 1; a[1] = true; int j = 1; int count = 1; for (int i = 2; i <= n; i ++){ if (s[i] >= f[j]){ a[i] = true; j = i; count ++; }else{ a[i] = false; }//Of if }//Of for return count; }//Of greedySelector }//Of class GreedySelector
结果显示
1->4 5->7 8->11 12->14
4 activities are successfully scheduled.
条件:活动按结束时间非递减排序
证明:
(a) 令
P
P
P 为活动全集,
A
=
{
a
1
,
a
2
,
…
,
a
k
}
⊆
P
A = \{a_1, a_2, \dots, a_k\} \subseteq P
A={a1,a2,…,ak}⊆P 为一个最优活动集合, 其中
f
[
a
1
]
<
f
[
a
2
]
<
⋯
<
f
[
a
k
]
f[a_1] < f[a_2] < \dots < f[a_k]
f[a1]<f[a2]<⋯<f[ak]. 由活动的相容性可知,
f
[
a
1
]
≤
s
[
a
i
]
f[a_1] \leq s[a_i]
f[a1]≤s[ai], 其中
2
≤
i
≤
k
2 \leq i \leq k
2≤i≤k. 将活动
a
1
a_1
a1 替换为活动
1
1
1 可得
A
′
=
{
1
,
a
2
,
…
,
a
k
}
A' = \{1, a_2, \dots, a_k\}
A′={1,a2,…,ak}. 由条件可知
f
[
1
]
≤
f
[
a
1
]
≤
s
[
a
i
]
f[1] \leq f[a_1] \leq s[a_i]
f[1]≤f[a1]≤s[ai], 其中
2
≤
i
≤
k
2 \leq i \leq k
2≤i≤k. 即
A
′
A'
A′ 为一个相容活动集合. 由于
∣
A
′
∣
=
∣
A
∣
\vert A' \vert = \vert A \vert
∣A′∣=∣A∣,
A
′
A'
A′ 也为一个最优活动集合. 因此, 活动
1
1
1 至少包含在某个最优解之内.
(b) 将活动
1
1
1 及与其冲突的活动从
P
P
P 中删除, 获得活动子集
P
′
P'
P′, 并讨论其活动安排问题. 由于
a
i
a_i
ai 不与活动
1
1
1 冲突,
a
i
∈
P
′
a_i \in P'
ai∈P′, 其中
2
≤
i
≤
k
2 \leq i \leq k
2≤i≤k. 又由于
a
2
,
…
,
a
k
a_2, \dots, a_k
a2,…,ak 相互不冲突, 所以
{
a
2
,
…
,
a
k
}
\{a_2, \dots, a_k\}
{a2,…,ak} 为
P
′
P'
P′ 中可安排的活动集. 即
P
′
P'
P′ 中至少可以安排
k
−
1
k - 1
k−1 个活动. 另一方面
P
′
P'
P′ 中不可能安排多于
k
−
1
k - 1
k−1 个活动, 否则加上活动
1
1
1,
P
P
P 中可安排的活动数将超过
k
k
k, 这与
A
A
A 是最优活动集合相矛盾. 因此,
{
a
2
,
…
,
a
k
}
\{a_2, \dots, a_k\}
{a2,…,ak} 为
P
′
P'
P′ 的最优活动集合.
综上所述, (a) 证明了贪心选择性质, (b) 证明了最优子结构. 因此算法的正确性得证.
在活动安排问题中, 还可以有其他的贪心选择方案, 但并不能保证产生最优解. 给出一个例子, 说明若选择具有最短时段的相容活动作为贪心选择, 得不到最优解.
字符出现的频率与其权值成正比,求使得平均码长最短的编码方案
例: 字符权重为:
45
,
12
,
13
,
5
,
9
,
16
45, 12, 13, 5, 9, 16
45,12,13,5,9,16, 构造哈夫曼树.
方案一 (所提供的代码使用本方案):
哈夫曼树的构造过程中, 其贪心策略是使权重最小的字符对应的节点在树中层次最深. 记字符集为
Σ
\Sigma
Σ, 字符
x
∈
Σ
x \in \Sigma
x∈Σ 的权重为
w
x
w_x
wx, 且
∑
x
∈
Σ
w
x
=
1
\sum_{x \in \Sigma} w_x = 1
∑x∈Σwx=1.
(a) 贪心选择性质. 不失一般性, 令权重最小的字符为
a
a
a. 现在需要证明存在最优二叉树, 使得
a
a
a 对应的节点深度最大. 假设
T
T
T 为一棵最优二叉树, 其中节点
x
x
x 的层次记为
T
x
T_x
Tx.
T
T
T 的平均编码长度为
L
(
T
)
=
∑
x
∈
Σ
w
x
T
x
(1)
L(T) = \sum_{x \in \Sigma} w_x T_x \tag{1}
L(T)=x∈Σ∑wxTx(1)
令深度最大的某个节点为
b
b
b, 即
T
b
=
max
x
∈
Σ
T
x
T_b = \max_{x \in \Sigma} T_x
Tb=maxx∈ΣTx. 现将
a
a
a 与
b
b
b 的位置互换, 获得新的二叉树
T
′
T'
T′. 则
T
′
T'
T′ 与
T
T
T 的编码长度差别由
a
a
a,
b
b
b 两个字符确定.
L
(
T
)
−
L
(
T
′
)
=
w
a
T
a
+
w
b
T
b
−
w
a
T
b
−
w
b
T
a
=
(
w
a
−
w
b
)
(
T
a
−
T
b
)
(2)
L(T) - L(T') = w_a T_a + w_b T_b - w_a T_b - w_b T_a = (w_a - w_b) (T_a - T_b)\tag{2}
L(T)−L(T′)=waTa+wbTb−waTb−wbTa=(wa−wb)(Ta−Tb)(2)
由于
w
a
≤
w
b
w_a \leq w_b
wa≤wb,
T
a
≤
T
b
T_a \leq T_b
Ta≤Tb,
L
(
T
)
−
L
(
T
′
)
≥
0
L(T) - L(T') \geq 0
L(T)−L(T′)≥0.
T
′
T'
T′ 也一定是最优二叉树.
因此, 将权重最小的字符放到树中最深层次是一个正确的贪心选择方案.
(b) 最优子结构. 不失一般性, 令某棵最优二叉树
T
T
T 中, 最深的一对节点对应的字符为
a
a
a 和
b
b
b. 令
Σ
′
=
Σ
∖
{
a
,
b
}
∪
{
z
}
\Sigma' = \Sigma \setminus \{a, b\} \cup \{z\}
Σ′=Σ∖{a,b}∪{z},
w
z
=
w
a
+
w
b
w_z = w_a + w_b
wz=wa+wb, 将
T
T
T 中对应于
a
a
a 和
b
b
b 节点删除之后的二叉树为
T
1
T_1
T1, 其中
a
a
a 所对应的原父节点对应于新字符
z
z
z. 需要证明
T
1
T_1
T1 为
Σ
′
\Sigma'
Σ′ 的最优二叉树.
假设
Σ
′
\Sigma'
Σ′ 的最优二叉树不是
T
1
T_1
T1, 则
∃
\exists
∃
Σ
′
\Sigma'
Σ′ 的另一棵二叉树
T
2
T_2
T2, s.t.
L
(
T
2
)
<
L
(
T
1
)
L(T_2) < L(T_1)
L(T2)<L(T1). 将
T
2
T_2
T2 的叶节点
z
z
z 扩展成
a
a
a 与
b
b
b 获得
T
3
T_3
T3, 则
T
3
T_3
T3 为原字母表
Σ
\Sigma
Σ 对应的一棵二叉树. 由于
a
a
a 与
b
b
b 的编码长度比
z
z
z 的多 1,
L
(
T
3
)
=
L
(
T
2
)
+
w
a
+
w
b
<
L
(
T
1
)
+
w
a
+
w
b
=
L
(
T
)
,
L(T_3) = L(T_2) + w_a + w_b < L(T_1) + w_a + w_b = L(T),
L(T3)=L(T2)+wa+wb<L(T1)+wa+wb=L(T), 这与
T
T
T 为最优二叉树的假设矛盾.
综上所述, (a) 证明了贪心选择性质, (b) 证明了最优子结构. 因此算法的正确性得证.
练习: 证明算法的正确性
证明:令无向图为
G
=
(
V
,
E
)
G = (\mathbf{V}, \mathbf{E})
G=(V,E), 其中
V
=
{
v
1
,
v
2
,
…
,
v
n
}
\mathbf{V} = \{v_1, v_2, \dots, v_n\}
V={v1,v2,…,vn},
E
=
{
e
1
,
e
2
,
…
,
e
m
}
\mathbf{E} = \{e_1, e_2, \dots, e_m\}
E={e1,e2,…,em}. 其生成树为
G
′
=
(
V
,
E
′
)
G' = (\mathbf{V}, \mathbf{E}')
G′=(V,E′), 其中
E
′
=
{
e
t
1
,
e
t
2
,
…
,
e
t
n
−
1
}
\mathbf{E}' = \{e_{t_1}, e_{t_2}, \dots, e_{t_{n-1}}\}
E′={et1,et2,…,etn−1}, 且
G
′
G'
G′ 为联通无环图.
(贪心选择性质)
不失一般性, 令起始节点为
v
1
v_1
v1, 贪心选择策略是找到与
v
1
v_1
v1连接边最短的节点, 以及相应的边. 记该点为
v
a
v_a
va, 相应的边为
e
b
=
(
v
1
,
v
a
)
e_b = (v_1, v_a)
eb=(v1,va). 现证明
e
b
e_b
eb 包括在某个最优解中.
令
G
′
G'
G′ 为一棵最小生成树, 其中不包括
e
b
e_b
eb. 则将
e
b
e_b
eb 加入
G
′
G'
G′ 中, 将形成一个环. 不考虑该环之外的节点, 每个节点的度刚好为 2. 令该环中与
v
1
v_1
v1 相关的另一条边为
e
c
e_c
ec, 则删除
e
c
e_c
ec 后, 获得另一棵生成树
G
′
′
G''
G′′. 由于
w
(
e
b
)
≤
w
(
e
c
)
w(e_b) \le w(e_c)
w(eb)≤w(ec),
G
′
′
G''
G′′ 也一定为一棵最小生成树.
(最优子结构性质)
算法正确性证明有一定的套路, 但写清楚并不容易.
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。