一.你对贪心算法的理解
贪心算法做出一系列局部最佳选择从而得到问题的解,类比前面所学的动态规划有所不同,贪心算法仅做出当前状态的最佳选择,动态规划要解出子问题再解这个选择之后产生的子问题。
二.请说明汽车加油问题的贪心选择性质
问题描述:
7-1 汽车加油问题 (15 分)
题目来源:王晓东《算法设计与分析》
一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法,指出应 在哪些加油站停靠加油,使沿途加油次数最少。
输入格式:
第一行有 2 个正整数n和 k(k<=1000 ),表示汽车加满油后可行驶n公里,且旅途中有 k个加油站。 第二行有 k+1 个整数,表示第 k 个加油站与第k-1 个加油站之间的距离。 第 0 个加油站表示出发地,汽车已加满油。 第 k+1 个加油站表示目的地。
输出格式:
输出最少加油次数。如果无法到达目的地,则输出“No Solution!”。
输入样例:
7 7
1 2 3 4 5 1 6 6
输出样例:
4
代码如下:
1 #include <iostream> 2 using namespace std; 3 int a[1000]; 4 int n,k; 5 int main(){ 6 cin>>n>>k;//可行驶公里&&加油站数 7 for(int i=0;i<=k;i++){ 8 cin>>a[i]; 9 } 10 int count=0; 11 int max=0; 12 int distance=n; 13 for(int i=0;i<=k;i++){ 14 if(distance-a[i]>=0){ 15 distance-=a[i]; 16 } 17 else{ 18 count++; 19 distance=n-a[i]; 20 } 21 if(max<a[i]){ 22 max=a[i]; 23 } 24 25 } 26 27 if(max>n){ 28 cout<<"No Solution!"; 29 } 30 else{ 31 cout<<count; 32 } 33 return 0; 34 }
该题运用的思想:每次行走的公里数与最大的相比较,若超过重新加油,否则就继续行驶,简单的判断做出选择。
三.请说明在本章学习过程中遇到的问题及结对编程的情况
在上机实践第二题卡了很久,花费了大量的时间,组队编程过程中发现答案正确但是一直无法通过。
题目描述:
4-2 删数问题 (110 分)
给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新 的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最 小的删数方案。
输入格式:
第 1 行是1 个正整数 a。第 2 行是正整数k。
输出格式:
输出最小数。
输入样例:
在这里给出一组输入。例如:
178543
4
输出样例:
在这里给出相应的输出。例如:
13
一开始想将输入的整数每一位数拆开后从小到大排序得到答案,但老师提醒不能打乱顺序,在课后最终做出来了,但花费的时间比较长。
自身的疑惑在于哈夫曼编码处的代码,需下功夫理解。