C++算法学习之贪心算法的应用

目录
  • 贪心1
    • 实验题目:减肥的小K1
    • 实验题目:最小跳数
    • 实验题目:排队接水
  • 贪心-堂练
    • 实验题目: 区间问题1
    • 实验题目:种树
    • 实验题目:智力大冲
    • 实验题目:删除数字II

贪心1

实验题目:减肥的小K1

题目描述:

小K没事干,他要搬砖头,为了达到较好的减肥效果,教练规定的方式很特别:每一次,小K可以把两堆砖头合并到一起,消耗的体力等于两堆砖头的重量之和。经过 n-1次合并后, 就只剩下一堆了。小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和。小K为了偷懒,希望耗费的体力最小。例如有 3堆砖头,数目依次为 1、2、9 。可以先将 1 、 2 堆合并,新堆数目为3 ,耗费体力为 3 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12 ,耗费体力为12 。所以总共耗费体力 =3+12=15。可以证明 15为最小的体力耗费值。

输入要求:

共两行。

第一行是一个整数 n(1≤n≤1000) ,表示砖头堆数。

第二行n个整数,每个整数表示每堆砖头的砖头块数。

输出要求:

一个整数,也就是最小的体力耗费值。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, a[1000], sum = 0, i;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    for (i = 0; i < n - 1; i++) {
        int temp = a[i + 1] + a[i];//记录前两个最小的值
        int k = i + 2;//k为第三个的下标
        while (a[k] < temp && k < n) {//比较第三个和前两个的和,若第三个比前两个要小
            a[k - 1] = a[k];//前移
            k++;
        }
        a[k - 1] = temp;
        sum += temp;
    }
    cout << sum << endl;
    return 0;
}

算法分析与知识点:

本题主要运用贪心的思想,每次都在全部砖头中找到重量最轻的两堆进行合并以达到最节约体力的目的。

因此要先对全部砖头按重量进行排序,需要注意的是再合并完两堆砖头后需要对后续砖头堆进行重新排序,第一次WA就是因为没有对后续砖头堆进行重新排序。

实验题目:最小跳数

题目描述:

给定一个非负整数数组,假定你的初始位置为数组第一个位置。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标位置,并且使用最少的跳跃次数。

输入要求:

输入一组非负整数数组,数组长度不超过500。

输出要求:

最少经过几次跳跃,可以到达最后一个位置。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 0, a[501];
    while (cin >> a[n++]);
    n = n - 1;
    // maxPos 记录当前最远能到哪里
    // step 记录当前进行了几跳
    // end 记录了当前最远能到哪里的边界
    int maxPos = 0, end = 0, step = 0;
    for (int i = 0;i < n - 1;i++) {
        if (maxPos >= i) { //判断能否继续探索
            maxPos = max(maxPos, i + a[i]);
            if (i == end) { // 到达边界更新跳数
                end = maxPos;
                step++;
            }
        }
    }
    cout << step << endl;
    return 0;

}

算法分析与知识点:

本题主要运用贪心的思想,在具体的实现中,我们维护当前能够到达的最大下标位置,记为边界。我们从左到右遍历数组,到达边界时,更新边界并将跳跃次数增加 1。

在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下,我们会增加一次「不必要的跳跃次数」,因此我们不必访问最后一个元素。

实验题目:排队接水

题目描述:

夏天到了,又到了用水高峰期,偏巧小区的水管出了点问题,消防车赶紧给小区送了一车水过来。小区居民们纷纷拿出自家装水的容器,有的是个大塑料瓶,有的是茶水壶,有的是小塑料桶,哈哈,什么样的都有:)。现在有n个人在一个水龙头前排队接水,假设每个人接水的时间分别为Ti,请编程找出这n个人排队的一种顺序,使得这n个人的平均等待时间最小。

输入要求:

输入有多组测试数据

每组测试数据共两行,第一行为一个整数n,表示有n个人;

第二行分别表示第1个人到第n个人每人的接水时间T1,T2,…Tn。

输出要求:

输出文件有两行,第一行为一种排队顺序,即编号从1到n的n个人的一种排序方式;

第二行为这种排序方案下的平均等待时间(输出结果精确到小数点后两位)。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;
struct person // 定义居民结构体,记录到来顺序及接水时间
{
	int id, time;
};
person p[1000];

bool cmp(person p1, person p2) { // 自定义结构体排序方法
	return p1.time < p2.time;
}
int main() {
	int n;
	while (cin >> n) {
		for (int i = 0;i < n;i++) {
			p[i].id = i;
			cin >> p[i].time;
		}
		sort(p, p + n, cmp); // 按接水时间升序
		double ans = 0;
		for (int i = 0;i < n - 1;i++) {
			cout << p[i].id + 1 << " ";
			ans += (n - 1 - i) * p[i].time;
		}
		cout << p[n - 1].id + 1 << endl;
		printf("%.2f\n", ans / n);
	}
	return 0;

}

算法分析与知识点:

本题主要运用贪心的思想,共有n名居民,他们所需的接水时间分别为 ,设他们的排队顺序为 ,可得出总共等待时间为

由以上公式可得要使得总的排队等待时间最短,就要按接水所需时间从小到大的顺序老排队接水。

贪心-堂练

实验题目: 区间问题1

题目描述:

给出n个区间的起点和终点,求最少使用其中多少个区间可以将所有区间所在的区域完全覆盖。(测试的数据确保这1点)。

输入要求:

第1行一个整数n,表示n个区间;

第2行开始n行,每行2个整数,表示一个区间范围。

类似[1,4] [5,6]被认为是覆盖了[1,6]。

输出要求:

从起点开始,按区间先后顺序,输出选中的区间。所选的区间应尽可能向终点扩展。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;

struct part//区间两端
{
	int star1, end1;
};

bool cmp(part s1, part s2) { // 自定义排序方式1、开始点升序,2、结束点升序
	if (s1.star1 < s2.star1)
		return true;
	else if (s1.star1 == s2.star1 && s1.end1 < s2.end1)
		return true;
	else
		return false;
}
int main()
{

	part a[100];//全部待选区间
	part r[100];
	//在a中选好的数放入r中

	int n, index = 0, i;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i].star1 >> a[i].end1;
	}

	sort(a, a + n, cmp);

	int right = a[0].star1 - 1;
	int end = a[n - 1].end1; // 待覆盖区间最远处

	for (i = 0; i < n - 1; )
	{
		int maRight = a[i].end1, maIndex = i;

		while (a[i].star1 <= right + 1 && i < n) { // 寻找最远子区间
			if (a[i].end1 > maRight) {
				maRight = a[i].end1;
				maIndex = i;
			}
			i++;  //比较完数组往后移
		}
		right = maRight;
		r[index++] = a[maIndex];
		i = maIndex;
		if (right == end)
			break;
	}
	for (i = 0; i < index; i++) {
		cout << r[i].star1 << " " << r[i].end1 << endl;
	}
	return 0;
}

算法分析与知识点:

思路:设置一个a[]数组保存原始的数据,设置一个人r[]数组保存被选的区间数据。

先按1、开始点升序,2、结束点升序将数据排序。为了使覆盖总区间的所需的子区间数最少,就要选出一系列覆盖范围最广的子区间。方式描述如下所示:初始令所能到达的范围为 ,然后选出一个子区间让这个范围尽可能向区间终点靠,即找到符合条件 的最远子区间。

实验题目:种树

题目描述:

一条街的一边有几座房子。因为环保原因居民想要在路边种些树,路边的地区被分割成块,并被编号成1…N;每个部分为一个单位尺寸大小并最多可种一棵树,每个居民想在门前种些树并指定了三个号码B,E,T,这三个数表示该居民想在B和E之间最少种T棵树。当然,B≤E,居民必须记住在指定区不能种多于区域地块数的树,所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入要求:

第一行包含数据N,区域的个数;

第二行包含H,房子的数目;

下面的H行描述居民们的需要:B E T。

输出要求:

输出能满足所有要求的最少的树的数。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;

int n, m, k, ans;
struct node // 保存要求数据
{
	int b, e, t;
}a[5005];
bool used[30005]; // 记录该位置是否种过树

bool cmp(const node& a, const node& b) // 自定义排序方式
{
	return a.e < b.e;
}

int main()
{
	cin >> n >> m;
	for (int i = 0;i < m;i++) // 输入数据
	{
		cin >> a[i].b >> a[i].e >> a[i].t;
	}
	sort(a, a + m, cmp);
	memset(used, 0, sizeof(used)); //初始化每个位置都没种过树
	ans = 0; // 记录所需树的数量
	for (int i = 0;i < m;i++)
	{
		k = 0;
		for (int j = a[i].b;j <= a[i].e;j++) // 求在该要求区间内已经种了多少树
		{
			if (used[j]) k++;
		}
		if (k >= a[i].t) // 未达到要求
			continue;
		k = a[i].t - k;  // 还要种的数量
		for (int j = a[i].e;j >= a[i].b;j--)
		{
			if (used[j] == false) // 寻找没种过的位置
			{
				used[j] = true;//种树
				ans++;
				k--;
			}
			if (k == 0)
				break;
		}
	}
	cout << ans << endl;
	return 0;
}

算法分析与知识点:

本题采用贪心算法的思想,要使所需的总树苗数量最小,就要让一个区间的树苗将可能的能满足更多的用户要求。这里采用让后面的居民尽可能为前面的居民着想,即在满足自己要求的前提下把树尽可能地往前面的位置种,这样可以让居民的要求重叠的范围更多,从而达到使用最少的树苗满足所有居民的要求。

为了达到目的,我们需要先将居民按提出要求的开始区间点排序,然后从后往前尽可能地为前面地居民考虑。考虑满足第i个居民方式:要先考虑满足第i+1个居民的要求后里自己的要求还差多少,然后由于为第i-1个居民着想的目的,将未满足要求的树苗种在第i个居民要求区间的前面。

实验题目:智力大冲

题目描述:

小伟报名参加中央电视台的智力大冲浪节目,本次挑战赛吸引了众多参赛者,主持人为了表彰大家的勇气,先奖励每个参赛者m元。先不要太高兴!因为这些钱还不一定都是你的!接下来主持人宣布了比赛规则:

首先,比赛时间分为n个时段(n≤500),它又给出了很多小游戏,每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成,则要从奖励费m元中扣去一部分钱wi,wi为自然数,不同的游戏扣去的钱是不一样的。当然,每个游戏本身都很简单,保证每个参赛者都能在一个时段内完成,而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟很想赢得冠军,当然更想赢取最多的钱!注意:比赛绝对不会让参赛者赔钱!

输入要求:

输入文共4行。

第1行为m,表示一开始奖励给每位参赛者的钱

第2行为n,表示有n个小游戏;

第3行有n个数,分别表示游戏1到n的规定完成期限;

第4行有n个数,分别表示游戏1到n不能在规定期限前完成的扣款数。

输出要求:

输出仅1行,表示小伟能赢取最多的钱。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, f[N];
struct node {
    int t, w;
}a[N];
int cmp(node x, node y) { return x.w > y.w; } // 自定义排序方式
void work()
{
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1;i <= n;i++)
    {
        bool pd = false;  // 判断该游戏是否被完成
        for (int j = a[i].t;j >= 1;j--)
        {
            if (f[j] == 0) //可以安排这个游戏
            {
                f[j] = 1;
                pd = true;
                break;
            }
        }
        if (pd == false) m -= a[i].w;
    }
}
int main()
{
    cin >> m >> n;
    for (int i = 1;i <= n;i++) cin >> a[i].t;
    for (int i = 1;i <= n;i++) cin >> a[i].w;
    work();
    cout << m << endl;
    return 0;
}

算法分析与知识点:

本题采用贪心算法的思想,首先将所有游戏按其价值从高到低排序。一个游戏只要在规定期限完成之前完成就不会被扣除奖励,为了让一个游戏尽可能不影响其他游戏,我们让其在自己的规定期限内尽可能地往后靠。我们从奖励价值最高的游戏开始考虑,将所有游戏考虑完成后就可以得到的所获得的奖励最大值。

实验题目:删除数字II

题目描述:

在给定的n个数字的数字串m中,删除其中k(k< n)个数字后,剩下的数字按原次序组成一个新的整数。请确定删除方案,使得剩下的数字组成的新整数最小。(1<=k<n<=240)

输入要求:

输入有一行,先输入数字串m,再输入k,如描述所示。

保证数字串m没有前导0。

输出要求:

输出有两行,第一行按顺序输出从左到右删除的k个数字,用空格隔开。(第一行里的输出顺序是按照被删除数字在原数中的顺序排列的,而不是按照删除的顺序排列的)

第二行输出删除k个数字后剩下的数字组成的新数,并换行。

实验代码及注释:

#include <bits/stdc++.h>
using namespace std;
struct node // 记录被删除数字的内容及下标
{
    char c;
    int index;
}temp[300];
bool cmp(node a, node b) { // 自定义排序方式
    return a.index < b.index;
}
int main()
{
    string s, t;
    int k;
    vector<int> index; //下标数组
    cin >> s >> k;
    for (int i = 0;i < s.length();i++) //初始化下标数组
        index.push_back(i);
    for (int i = 0;i < k;i++) {
        int j;
        for (j = 0;j < s.length() - 1;j++) { // 寻找要删除哪个数字
            if (s[j] > s[j + 1]) {
                break;
            }
        }
        temp[i].c = s[j]; // 记录被删除数字的内容
        temp[i].index = index[j]; // 记录被删除数字在原数字中的位置
        s.erase(j, 1);
        index.erase(index.begin() + j);
    }
    sort(temp, temp + k, cmp);//将删除的数字按其在原数字中的位置排序
    for (int i = 0;i < k - 1;i++)
        cout << temp[i].c << " ";
    cout << temp[k - 1].c << endl;
    while (s[0] == '0')
        s.erase(0, 1);
    if (s.length() == 0)
        s = "0";
    cout << s << endl;
    return 0;
}

算法分析与知识点:

本题采用贪心算法的思想,要删除k个数字的中的数字字符串后数字最大,就要让每次删除一个字符后留下来的数字都要是当下的最小值。

为了找到一个字符,将其删除后让留下来的数字最小,被删除的数字要满足条件如下:

从数字字符串从高位到低位第一个变小的数字。

上述数字的第一次删除就应该删除数字8.

以上就是C++算法学习之贪心算法的应用的详细内容,更多关于C++贪心算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++贪心算法实现马踏棋盘

    本文实例为大家分享了C++贪心算法实现马踏棋盘的具体代码,供大家参考,具体内容如下 算法实现流程: 步骤1:初始化马的位置(结构体horse {x, y}) 步骤2:确定马从当前点出发,可跳跃的附近8个点,以结构体Jump数组给出,但需判断当前给出的附近8个点是否曾经访问过,或者是否这8个点超出棋盘尺寸. 步骤3:跟据步骤2确定跳跃的点,分别计算可跳跃点的下下一步,可跳跃点的个数.并选出下下步可跳跃点数最少的点作为马下一步跳跃的点.(举例说明:马当前所在点坐标(4,4),下一步可跳跃点有(5,2

  • C++ 算法精讲之贪心算法

    目录 选择排序 平衡字符串 买股票的最佳时机 跳跃游戏 钱币找零 多机调度问题 活动选择 无重叠区间 选择排序 我们熟知的选择排序,其采用的就是贪心策略. 它所采用的贪心策略即为每次从未排序的数据中选取最小值,并把最小值放在未排序数据的起始位置,直到未排序的数据为0,则结束排序. void swap(int* arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void selectSort(int* a

  • C++贪心算法实现活动安排问题(实例代码)

    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 具体代码如下所示: #include <cstdio> #include <iostream> #include <ctime> #include <

  • C++ 搬水果贪心算法实现代码

    C++ 搬水果贪心算法实现代码 (1)题目描述: 在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆.每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和.当然经过 n‐1 次合并之后,就变成一堆了.小明在合并水果时总共消耗的体力等于每次合并所耗体力之和. 假定每个水果重量都为 1,并且已知水果的种类数和每种水果的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值.例如有 3 种水果,

  • 采用C++实现区间图着色问题(贪心算法)实例详解

    本文所述算法即假设要用很多个教室对一组活动进行调度.我们希望使用尽可能少的教室来调度所有活动.采用C++的贪心算法,来确定哪一个活动使用哪一间教室. 对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少. 具体实现代码如下: //贪心算法 #include "stdafx.h" #include<iostream> #define N 100 using namespace std; struct Activity { int n

  • C++算法学习之贪心算法的应用

    目录 贪心1 实验题目:减肥的小K1 实验题目:最小跳数 实验题目:排队接水 贪心-堂练 实验题目: 区间问题1 实验题目:种树 实验题目:智力大冲 实验题目:删除数字II 贪心1 实验题目:减肥的小K1 题目描述: 小K没事干,他要搬砖头,为了达到较好的减肥效果,教练规定的方式很特别:每一次,小K可以把两堆砖头合并到一起,消耗的体力等于两堆砖头的重量之和.经过 n-1次合并后, 就只剩下一堆了.小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和.小K为了偷懒,希望耗费的体力最小.例如有 3堆

  • Java贪心算法之Prime算法原理与实现方法详解

    本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

  • Python 经典贪心算法之Prim算法案例详解

    最小生成树的Prim算法也是贪心算法的一大经典应用.Prim算法的特点是时刻维护一棵树,算法不断加边,加的过程始终是一棵树. Prim算法过程: 一条边一条边地加, 维护一棵树. 初始 E = {}空集合, V = {任选的一个起始节点} 循环(n – 1)次,每次选择一条边(v1,v2), 满足:v1属于V , v2不属于V.且(v1,v2)权值最小. E = E + (v1,v2) V = V + v2 最终E中的边是一棵最小生成树, V包含了全部节点. 以下图为例介绍Prim算法的执行过程

  • java贪心算法初学感悟图解及示例分享

    算法简介 1)贪心算法是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致是最好或者最优的算法 2)贪心算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果. 应用场景 --> 集合覆盖 public class GreedyAlgorithm { public static void main(String[] args) { // 创建广播电台,放入到Map HashMap<String, HashSet<

  • Java 数据结构与算法系列精讲之贪心算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法 贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单 缺点: 很难确定一个问题是否可以用贪心算法解决 电台覆盖问题 假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台 覆盖地区 K1 北京

  • 浅谈Python实现贪心算法与活动安排问题

    贪心算法 原理:在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解.贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解. 特性:贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不

  • python算法学习之计数排序实例

    python算法学习之计数排序实例 复制代码 代码如下: # -*- coding: utf-8 -*- def _counting_sort(A, B, k):    """计数排序,伪码如下:    COUNTING-SORT(A, B, k)    1  for i ← 0 to k // 初始化存储区的值    2    do C[i] ← 0    3  for j ← 1 to length[A] // 为各值计数    4    do C[A[j]] ← C[A

  • c语言来实现贪心算法之装箱问题

    装箱问题,贪心算法求近似最优解 复制代码 代码如下: import java.util.Arrays; import java.util.Comparator; //装箱问题,贪心算法 public class Enchase {     public void test1() {         Integer[] boxs={34,6,40,2,23,12,12};         int boxCaptation=40;//箱子容量         //倒序         Arrays.

随机推荐