第四章总结

1. 你对贪心算法的理解

2. 请说明汽车加油问题的贪心选择性质

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

1. 对贪心算法的理解

贪心算法是计算局部最优解，所以如果我们要求的全局最优解，那么我们的全局最优解要包含局部最优解。通常使用到循环结构和sort函数进行数据的排序。贪心算法是一个比较高效的算法。

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

首先汽车加满油后行驶的路程是有限的，所以如果出现两地间的距离大于这个最大行驶距离的话，是无法到达目的地的，那么我们要计算至少需要加多少次油，我们就要先记录每次不够到达下一个目的地时，

当前走到的路程，通过循环计算就可得到结果了。

代码（C++)：

#include<iostream>
using namespace std;
int main(){
    int n,k;
    int a[1000];
    int count = 0;
    cin>>n>>k;
    for(int i = 0;i <= k;i++){
        cin>>a[i];
    }
    int temp = n;
    for(int i = 0;i <= k;){
        if(a[i]<=n) {
            if(temp >= a[i]){
                temp = temp -a[i];
                i++;
            }
            else {
                count++;
                temp = n;
            }
        }
        else {
            cout<<"No Solution!"<<endl;
            return0;
        }
    }
    cout<<count<<endl;
    return0;
} 

3. 本章学习中遇到的问题及编程出现的问题

本章的算法的难点在于找到最优子结构，例如会场安排问题对于时间的安排，背包问题等等。

第四章总结

原文：https://www.cnblogs.com/coding-specification-of-Java/p/11925015.html