大白糖奶兔的Blog
大白糖奶兔的Blog
Chapter2-贪心算法
https://yczbest.cn/wp-content/uploads/2020/10/image-6.png
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	double c;
	int n;
	cout << "请输入载重总量及古董个数:";
	cin >> c >> n;
	int* a = new int(n);
	cout << "请输入每件物品重量,用空格隔开:";
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	double temp = 0.0; //装入物品总重量
	int ans = 0; //装入物品数量
	for (int i = 0; i < n; i++)
	{
		temp += a[i];
		if (temp <= 30)
			ans += 1;
		else
			break;
	}
	cout << "共能装下" << ans << "件物品" << endl;
	return 0;
}
https://yczbest.cn/wp-content/uploads/2020/10/image-7-1024x125.png

背包问题

https://yczbest.cn/wp-content/uploads/2020/10/image-8-1024x312.png
#include<algorithm>
#include<iostream>
using namespace std;
struct Node {
public:
	double prize;
	double weight;
	double value;
	Node() {
		this->prize = 0;
		this->weight = 0;
		this->value = 0;
	}
	Node(double p,double w) {
		this->prize = p;
		this->weight = w;
	}
};
bool cmp(Node& a, Node& b) {
	return (a.value > b.value);
}
int main() {
	bool cmp(Node & a, Node & b);
	int c,n;
	double w, p, v;
	cout << "请输入总载重量及物品个数:";
	cin >> c >> n;
	cout << "请依次输入物品价格和重量,输入完一种物品按一下Enter:\n";
	Node* a = new Node[n];
	for (int i = 0; i < n; i++)
	{
		w = p = v = 0;
		cin >> a[i].prize;
		cin >> a[i].weight;
		a[i].value = a[i].prize / a[i].weight;
		cout << " 价格: " << a[i].prize << " 重量: " << a[i].weight << " 性价比: " << a[i].value << endl;
	}
	sort(a, a + n, cmp);
	double sum = 0.0; //运走物品价值之和
	//计算性价比
	for (int i = 0; i < n; i++)
	{
		if ( c > a[i].weight) {//物品重量小于总载重量
			c -= a[i].weight;// 总量减去性价比最大物品的总重量
			sum += a[i].prize; //直接加总价值
		}
		else {
			sum += c * a[i].value; //重量*每重量的性价比
			//无论什么物品、不能全部装入就用剩下的容量能装多少装多少
			break;
		}
	}
	sort(a, a + n, cmp);
	cout << "价值最大化:" << sum;
	return 0;
}

https://yczbest.cn/wp-content/uploads/2020/10/image-9-1024x449.png

会议安排

https://yczbest.cn/wp-content/uploads/2020/10/image-10.png
#include<iostream>
#include<algorithm>
using namespace std;
struct Meet {
public:
	int start_time;
	int end_time;
	int index;
	Meet() { this->start_time = this->end_time = this->index = 0; }
	Meet(int start_time, int end_time) {
		Meet(start_time, end_time);
	}
};
bool cmp_end(Meet a,Meet b) {
	return (a.end_time < b.end_time);
}
bool cmp_start(Meet a, Meet b) {
	return ((a.end_time == b.end_time) && (a.start_time > b.start_time));
}
int main() {
	void Search(Meet * m, int n);
	int n;
	cout << "请输入会议个数:";
	cin >> n;
	Meet* m = new Meet[n];
	cout << "请输入会议开始时间和结束时间,空格隔开:" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> m[i].start_time >> m[i].end_time;
		m[i].index = i + 1;
	}
	sort(m, m + n, cmp_end);
	sort(m, m + n, cmp_start);
	Search(m, n);
	return 0;
}
void Search(Meet* m,int n) {
	cout << "--------------------排序后的会议时间如下------------------" << endl;
	cout << "会议序号\t开始时间\t结束时间\t" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << m[i].index << "\t\t" << m[i].start_time << "\t\t" << m[i].end_time << endl;
	}
	cout << "-------------------选择会议-------------------" << endl;
	int last = m[0].end_time;
	cout << "选择了" << m[0].index << "号会议" << endl;
	//找大于或等于最早结束时间的开始时间的会议
	int ans = 1;
	for (int i = 0; i < n; i++)
	{
		if (m[i].start_time >= last) {
			ans += 1;
			last = m[i].end_time;
			cout << "选择了" << m[i].index << "号会议" << endl;
		}
	}
	cout << "最多安排" << ans << "场会议" << endl;
}

发表评论

textsms
account_circle
email

大白糖奶兔的Blog

Chapter2-贪心算法
#include<iostream> #include<algorithm> using namespace std; int main() { double c; int n; cout << "请输入载重总量及古董个数:"; cin >> c >> n; int* a = new in…
扫描二维码继续阅读
2020-09-29
Title - Artist
0:00