算法笔记-贪心

贪心算法还是蛮好理解的.

硬币问题

很简单的一个贪心问题是, 有各种面值不同(1元, 5元, 10元, 等等)的硬币各多少多少枚, 然后要用这些硬币支付N元, 问最少需要多少枚.

这个问题因为有1元的硬币所以是一定有解的, 跟前一篇DFS的部分和问题不同. 问最少的话那当然是从最大的硬币开始拿, 不够了再用小的补.

这个很简单略过.

补充条件, 假设一定有解. 一般是把这样的硬币问题当作背包问题, 但是如果能用贪心解的话会比用DP简单.

区间调度问题

有n项工作, 每项工作分别在s_i时间开始, 在t_i时间结束. 可以选择参加哪些工作, 但是一旦参加就必须完成. 而且参加工作的时间段不能重叠. 问最多能参加多少份工作.

比方说有5份工作, 开始时间是{1, 2, 4, 6, 8}, 结束时间是{3, 5, 7, 9, 10}

画图就是这样的:

所以选择1, 3, 5. 最多是3份.

那算法应该是怎样呢?

有三种可能:

• 每次选结束时间最早的
• 每次选用时最短的
• 每次选与最少可选工作有重叠的工作

简单的想, 既然是要最多那么如果结束时间最早的话就可以尽快开始下一个工作, 这样应该是最多的.(自己的想当然…><) 具体的证明可以看这篇文章.

参考C++代码:

修理栅栏POJ3253

POJ原题: 3253

大致题意是说一块很长的木板要切成N块, 但是每次切割的时候会有开销, 开销等于切的这块木板的长度. 问怎样切使得开销最小.

例如长度为21的木板要切成8, 5, 8这样三块. 第一次切成8和13, 开销为21; 第二次切成5和8, 开销为13. 总开销即为21 + 13 = 34.

这个问题其实是哈夫曼编码的问题~ 哈夫曼编码根据词频来画二叉树, 这个题目就是根据木板长度来画二叉树.

那么就是先找出最短的两块, 相加为最后一次的开销, 然后假设这两块合成一块放到原来的木板中再找出最短的两块, 相加为倒数第二次的开销, 以此类推直到所有木板合成一块就是第一次的开销, 把所有的开销加起来就是总开销.

参考C++代码:

comments powered by Disqus