贪心算法(中英对照版）

贪心算法

性质：

1. 不具备固定的模式或类型
2. 基于当前状态的最优解能够得到整体解决方案
3. 这种方法仅适用于某些特定问题（其中局部优化能够实现全局最优）
4. 贪心策略在其核心位置起着决定性作用

总结：即通过建立数学模型来描述问题，并采用while循环将复杂问题分解为若干子问题；然后采用合理的方法计算各子问题的最优解；最后综合各子问题的最优解来确定整体解决方案。

每年秋天这棵树都会结果实约N枚(其中 N 的取值范围是 [1, 1\text{e}6])。
当她的手臂无法直接接触果实时
她会选择使用一块35厘米高的木板凳
以此帮助自己更好地完成采摘工作。
根据当前气象条件
已知N枚从地面量起的高度数据
以及她在手伸展极限状态下能达到的最大高度
请计算并返回在此情况下
她能采摘的成功数量。
假设在采摘过程中一旦碰到任何果子
该果子将立即掉落至地面。
接下来是程序运行所需的输入格式：
第一行为数据总量N+1值
其中第二项至第N+1项为对应各枚果子的高度信息（单位：厘米）
第二行为最大可及高度值（单位：厘米）。
程序运行结束后
将输出结果由一行单独给出。
代码如下：

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
    int i,j,m,b,sum,n;
    scanf("%d",&n);
    sum=0;
    int a[1000]= {0};
    for(i=0; i<n; i++)
    {
        scanf("%d",&m);
        a[m]++;
    }
    scanf("%d",&b);
    for(i=100; i<=b+30; i++)
    {
        sum+=a[i];
    }
    printf("%d\n",sum);
    return 0;
    }

谢谢观看，下次再见！

（English）

Greedy Algorithm

Nature:

No fixed form

Select an optimal solution for addressing the existing circumstances, and subsequently determine a comprehensive strategy to achieve long-term goals.

Only a minority of issues (through local strategies, one can achieve global optimal solutions)

The key is the choice of greedy strategy.

Train of thought:

I drew it myself! Summary: 将问题建模为一个数学模型，并通过循环分解的方法将其分解为多个子问题。随后通过可行解法找到了各个子问题的最优解，并最终推导出整体最优解。

Example:

Tao Tao's yard possesses an apple tree. Each autumn yields N apples (wherein 1 < N < 1,000,00). Once the fruit ripens, Taotao will rush to collect them. She usually utilizes a stool that stands at 3 decimeters. Should she find it difficult to reach the fruit without assistance, she will sit on the bench and attempt once more.

Currently, we have determined the elevation of N apples relative to the ground and Taotao's maximum reach when she extends her hand. Please assist Taotao in calculating how many apples she can pick. If Taotao touches an apple, it will fall to the ground.

input

The input comprises two lines of data. The first line includes an integer (N) followed by N height measurements in centimeters, all ranging from 100 to 200, which correspond to the heights of apples relative to the ground. The second line provides a maximum height measurement in centimeters attainable by the pottery handle when stretched, with this value falling within the range of 100 to 120 centimeters.

output

The output is a line that includes only a single integer, signifying the number of apples Taotao is able to harvest.

The code is as follows:

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
    int i,j,m,b,sum,n;
    scanf("%d",&n);
    sum=0;
    int a[1000]= {0};
    for(i=0; i<n; i++)
    {
        scanf("%d",&m);
        a[m]++;
    }
    scanf("%d",&b);
    for(i=100; i<=b+30; i++)
    {
        sum+=a[i];
    }
    printf("%d\n",sum);
    return 0;
    }

Thanks for watching,see you!