第四章作业

1. 贪心算法的理解

贪心算法总是做出在当前看来是最好的选择，贪心算法并不是从整体最优上加以考虑，它所做出的的选择只是在某种意义上的局部最优选择.

即在当前状态下做出最好的选择，，再去解出这个选择后产生的子问题.

2. 汽车加油问题的贪心选择

为了使加油的次数最少，我们的贪心选择应该是在每次前行时，检查当前的油是否足够行驶到下一站，够则不加，不够则加.

C++代码：

#include <iostream>
using namespace std;
int main()
{
int n;
int k;
cin>>n>>k;
int a[k+1];
for(int i=0;i<(k+1);i++)
{
cin>>a[i];
}
int can=n;
int count =0;
int flag=0;
for(int i=0;i<(k+1);i++)
{
if(i<k){
if(a[i]<=can)
{
can = can-a[i];
if(a[i+1]>can)
{
count++;
can = n;
}
}
else
{
cout<<"No Solution!";
flag = 1;
break;
}
}

}
if(flag==0)
cout<<count;

}

3. 结对编程

由于贪心算法是一种比较直观，容易想到的方法，所以本章遇到的问题并没有动态规划的问题那么大.

第四章作业

原文：https://www.cnblogs.com/yingyingguai/p/10049116.html