第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
哈工大硕士 算法作业4 贪心 答案.docx
1、(1).贪心策略：按照加满油需要的时间从小到大对 C 中的汽车进行排序，得到一个新的序
列 '
'
2,
c c
1
c…… ，按照此顺序进行加油得到的平均等待时间最短。
'
n
,
(2).
贪心选择性：
引理 1：要使得平均等待时间最短，则总的等待时间 T 也必须最短，故第一辆加油的汽车对
应的加油时间 min
t 必然最短。
证明：假设第一辆加油的汽车的加油时间不是最短，即
't
t 。
min
t 对应的汽车必然在后面加油的某一辆汽车中，不妨设其为第 k 辆汽车，其他汽车的加
则 min
油顺序不改变，则新的总等待时间 'T 满足：
T’-T=
n
i
1
n
i
1
t
j
i
1
j
1
i
1
j
1
t
'
j
((
n
1)
t
min
(
'
) )
n k t
((
n
'
1)
t
(
)
n k t
)
(
k
1)(
t
min
min
'
t
) 0
由于 1k ，
't
t ，故上式成立，此时 'T
min
T ，因而不再满足最短等待时间的要求，故
不符合要求，假设不成立，即引理 1 成立
优化子结构：
引理 2：对于需要等待加油的汽车集合C ，若加油顺序 A 是其一个优化解且第一个加油的车
辆为 1C ，则
A t 是
1{ }
C c
的一个解。
1{ }
证明：设 'B 为
1{ }
C c
的解，由于
A
A
'
t
1
,
B
B
' 1
A
，与 A 最小矛
' 1
A
盾，故引理 2 成立
(3).伪代码及算法复杂度:
算法：求解最短平均等待时间 avgt
输入：等待时间序列T ，车辆序列C
输出：最短平均等待时间 avgt 和等待车辆序列 'C
_
shortest
time T C
);
(
n
size C
,
( ,1,
Quick T
n C
1
n
1
i
,
C
return t
(
) ;
n i t
i
( ,
) :
);
avg
t
'
avg
) :
;
,
j C
,
j
T temp
partiti
( , ,
Quicksort
i
T
temp
rand i
;
x
, ,
k
on T i
,
, ,
QuickSort T i k C
,
1,
k
QuickSort
T
,
,
j x C
;
,
j C
;
;
:
,
, ,
,
Partition T i
j x C
;
;
i high
low
j
While low high Do
, T
swap
low
high
T
);
(
,
swap c
c
high
low
T
While
low
x Do
1;
low
low
T
low
While
high
high
return high
x Do
;
1
时间复杂度：即为快速排序的时间复杂度， ( lg )
O n
n 。
2、(1).贪心策略：每次选择最轻的两堆进行合并。
(2).贪心选择性：本题实质上和哈夫曼编码问题一致，即如果按照哈夫曼编码的方式对不同
堆的石子进行划分，即可得到最小代价的哈夫曼树，将树中各节点的代价相加即可得到需要
的总的代价。故以下贪心选择性和优化子结构将按照哈夫曼编码的证明方式进行：
引理 1. 设 N 是石子堆， i 、 j 是 N 中具有最小重量的两个石子，则存在一个 N 的优化前
缀树，i 与 j 的编码具有相同长度，且仅在最末一位不同。
证明：设T 是 N 的优化前缀树，且b 和 c 具有最多被选择次数的两个石子：
不失一般性，设 ( )
f b
j 是具有最小重量的两个石子，交换T 的b
( )
( ),
f c f i
因为 ,i
( )
j
f
和i 得到 'T ，再交换 c 和 j 得到 ''T ， 往证 ''T 是最优化前缀树。
'
T
T
( )
c
( )
f c d
(
')
B T
( )
( )
f c d c
( )
B T
c N
c N
( )
( )
( )
( )
( )
( )
i d i
f
f b d b
i d i
f
'
T
T
( )
( )
( ))(
( ))
(
d x
d b
f x
f b
T
T
( ),
( )
( )
( )
d x
f x d b
f b
T
( )
(
')
B T
B T
T
T
( )
( )
f b d b
T
'
同理， (
B T
')
(
B T
'')
，故 ( )
B T
(
B T
'')
，由于T 是最优化的，所以 ( )
B T
(
B T
'')
故 ''T 也
是最优化的，得证。
优化子结构：
引理 2：设T 是石子堆 N 的优化前缀树，设 x 、 y 是T 中任意两个相邻叶节点， z 是它们
的父节点，则 z 作为出现次数和的节点，则 '
T
T
{ , }
x y
是石子堆 '
N
N
{ , } { }
x y
z
的优化前缀树。
''')
( )
f x
( )
f y
,
w…
n
( )
f y
( )
f y
(
B T
')
(
B T
'')
(
B T
')
( )
f x
( )
B T
( )
f x
w w
2
,
证明：首先 ( )
，若 'T 不是优化前缀编码树，则必然存在 ''T ，使
B T
其为代价较低。因为 z 是 'N 中字符，它必然为 ''T 中的叶子，把节点 x 与 y 加入 ''T 作为 z
的子节点，得到一个 C 的前缀编码树 '''T ，代价为
(
B T
与T 是优化的矛盾，所以 'T 是 'N 的优化编码树。
(3).伪代码及复杂度分析：
算法：求解最小的总代价 Cost
输入： n 个石子及对应的重量 1
输出：最小总代价Cost ：
_
Min Cost n W
min_
heap W
0;
Cost
(
while size
a
delete
b
delete
temp
Cost
Insert temp
;
retur
heap
min_heap[1];
(min_
heap
[1];
min_
(min_
heap
;
a b
temp Cost
,min_
(
n Cost
heap
);
(min_
( ,
) 1)
heap
[1]);
[1]);
)
;
时间复杂度分析：要做 2(
n 次维护堆的操作，每次的时间复杂度是 lg n ，故总的时间复
1)
杂度为 ( lg )
n
O n
3、(1).贪心策略：将权重作排序，每次选择权重最大的人 i 作为先分到糖果的人，分到糖果
后，将其权重变为其邻居中权重最大的那个，然后重新作排序和选择。最后所有人的权重达
到一致，对每个人分一块糖果。
(2).正确性分析：首先通过先给权重较大的人分糖果，保证了权重大的人分到的糖果多，同
时每次使权重下降达到可以到达的最大值（当前权重-最大邻居权重），并且对于每次操作来
说，这种权重下降都是最大的，因而保证了最大下降的速度，即糖果分配的次数达到了最小；
最后，对整个队列中所有的样本均做一次糖果分配，满足了所有人必须分到一块糖果这个条
1
…
;
(
,
) :
)
;
w
N
count N
件，从而在满足题目中给定条件的情况下，实现了最小糖果分配的方案。
(3).伪代码及时间复杂性分析：
算法：求解最小糖果分配方案，使每个人都能分到糖果的同时，权重高的人能够分到比邻居
更多的糖果。
输入：权重W ，人数 N ，
输出：最小需要的糖果数 m
_
Min num W N
0;
count
(
If w w
2
count
;
return count
:
for all w in w
;
w w w
i
i
min
count
count N
0 :
while w
(
argmax w
j
i
;
p
w first less than w
j
q
w first larger than w
q
,
for all w do
j
(
,
w max w w
w
j
j
q
p
( );
count
size j
count
return count
);
p
:
;
j
i
i
);
;
时间复杂度：可建立最小堆对其进行维护，每次维护开销为 lg n ，总计需要 n 次，因而时间
复杂度为 ( lg )
n
O n
4、(1).贪心策略：将 A 和 B 均按照从大到小的顺序排列，然后按照 ia 和 ib 进行一一对应得
到的映射可以使整个代价最大
(2).贪心选择性：要使整个代价最大，则 A 中最大元素 maxa 和 B 中最大元素 maxb 必须是对应
的关系。
假设 maxa 和 maxb 不是映射中一一对应的关系，则至少存在 'a 和 'b ，使得 maxa 的映射对象是
'b ， maxb 的映射对象是 'a ，则在其他不变的情况下，总代价的变化如下所示：
L L
'
b
a
max
max
a
'
'
b
b
( '
a
max
'
b
a
max
)
'
b
a
max
(
b
a
max
max
b
'
1)
a
b
'
' ( '
b
a
max
b
'
1) 0
故总代价一定是不会增大的，故原方法必然可以使代价函数达到最大。
优化子结构：若映射 :f A
B 是一个优化解且其中最大的元素分别为 maxa 和 maxb ，则
{
':
f A a
}
B
{
b
max
}
max
是子问题的一个解。
证 明 ： 设 ''f 为 子 问 题 的 一 个 解 ， 由 于
f
f
'
({
a
}
{
b
max
})
max
，
f
''
({
a
}
{
b
max
})
f
'
({
a
}
{
b
max
})
max
max
，这与 f 是最优解矛盾，因而优化子
f
结构证明完毕。
(3).伪代码
算法：求解代价最大的一一映射 f
输入：集合 A ，集合 B
输出：代价最大的一一映射 f
) :
,
(
max_
map A B
(
);
n
size A
(
,1, );
Quick A n
(
,1, );
Quick B n
'
:
f A
B
return f
'
j
;
:
( , , )
Quicksort T i
j
,
temp
rand i
j
;
T temp
x
,
, ,
k
partition T i
j x
, ,
;
QuickSort T i k
1
,
,
T k
Quick
,
j x
Sort
, ,
:
Partition T i
;
;
low
i high
j
While low high Do
, T
low
T
swap
high
T
low
While
x Do
1;
low
low
T
low
While
high
high
return high
x Do
;
1
;
;
时间复杂度：即为快速排序的时间复杂度， ( lg )
O n
n 。
5、(1).贪心策略：按照性价比最高，即 /i
v w 的顺序对整个物品进行排序，然后按照从大到
i
小的顺序依次选择物品放入背包，直到背包达到满为止。
(2).贪心选择性：若要使背包中物品的价值最高，则第一个选取的必然是单位重量价值最高
的物品。
证明：假设第一个选取的不是单位重量价值最高的物品，则该物品在后面要么被选取一部分
或者全部，或者全部不选取，则对应的，第一个选择的物品的平均价值 'avgv 必然满足
v
'avg
v ，在其他条件不变的情况下，选取的价值差满足以下式子：
avg
V V
'
v
avg
*
w v
1
'
avg
w
2
( ' * '
v
w
2
avg
v
avg
* ' )
w
1
由于
v
avg
v
'
avg
w
且 2
w w w
，故
' ,
2
'
1
1
V V
' 0
，故贪心选择必然会使价值函数达到最
大值，因而贪心选择性成立。
优化子结构：若有一个优化解 S 包括单位价值最大的物品i ，选择的重量为 w ，则对问题
n
是子问题C w 的一个解。
i ，C w ，则 { }
{ }
i
S
证明：若 { }
i
S
不是子问题C w 的一个解，则一定存在一个解 'S ，则 ' { }
i
S
的对应解
的价值一定大于原解，因而与 S 是原问题的最优解有冲突，故矛盾，原命题得证。
(3).算法：求解在背包容量的限制下，能装载的东西的最大价值 V
输入：背包容量C ，每个物品的重量 iw 和价值 iv
输出：每件物品所选取的比例向量 1
,
x x
2
,
x
…,
n
,0
x
i
1
[ ]
i
avg
j
[1:
[1:
n
])
n
]);/ /
order
中记录排序的下标
[1:
(
,
1
:
for i from to n
/
;
v w
i
i
],
[1:
n Order
_
],
Max Value C W n V
V
avg
(
Sort V
0;
j
[1:
]
0;
n
x
0 & &
(
while C
V
avg
(
0)
if C w
[
[ ]] 1;
x order j
1;
j
C C w
[
return x
由于涉及到排序，且排序为时间复杂度的主要来源，因而采用最快的快速排序算法，时间复
x order j
[1:
;
[ ]
order j
;
[ ]
order j
C w
/
[ ]]
else
[ ]
order j
n
];
!
[])
杂性为 ( lg )
n
O n
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
