第四章贪心算法

1.你对贪心算法的理解                                                                           

贪心算法跟动态规划一样，都是解决最优化的问题。而求解最优化问题通常又是通过一系列的求解子问题的步骤。贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解，并不能保证得到最优解。可是如果得不到最优解，那就不是我们想要的东西了，所以我们在用贪心算法解决问题时要证明在这个问题中，用贪心法能得到最优解。

2.请选择一道作业题目说明你的算法满足贪心选择性质

我选择的是汽车加油问题

大致算法如下：

for(int i=1;i<=k;i++)
    {
        t+=distance[i];
        if(t+distance[i+1]>n)    
        {
            count++;
            t=0;
        }
        if(distance[i]>n)
            {
                cout<<"No Solution!"<<endl;
                return 0;
            }    
    }

使车在在有油的前提下，有得越远越好，这就是贪心算法，选择目前最好的选择。

其满足贪心选择性质，

汽车加满油能走m米，各个相邻站距离分别为x1，x2,x3...xk

其中x1+x2<m,x1+x2+x3>m

假设，（x1，xi...)为一个满足贪心选择性质的最优解，其加油站数为n，

因为x1+x2<m，

而（x2，xi....）也满足，且加油站数小于等于n

则该算法满足贪心选择性质

3.请说明在本章学习过程中遇到的问题及结对编程的情况

我的结对伙伴是何雨婷，这次还是她负责打代码，我在旁观看。有些题何不会那么快想出来，而我先想出来了，我会解释给她听，而为了让其更好地理解，我会先把思路捋清楚再叙述，而她也能根据我的思路把算法打出来。我觉得这是很大的一个收获吧，自己懂不是真的懂，能给别人讲明白才是真正的领悟到了。

第四章贪心算法

原文：https://www.cnblogs.com/hhue/p/13974461.html