算法题目打卡：Ques20201012

一、活动安排问题

1. 问题描述

 活动安排问题，一个场地，安排尽量多的活动。

2. 代码

// 活动安排

// 算法描述：①按照结束时间从大到小排序-->②优先安排结束时间早的-->③判断下一个活动的相容性的方法是f[i]>s[j]

// 关键词：贪心


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity
{
	int startTime;
	int finishTime;
	int label;
};
class Ques20201012
{
public:
	/*vector<Activity> activities;
	
	Ques20201012(vector<int> start, vector<int> finish) {
		Activity ac = Activity();
		for (int i = 0; i <= start.size();i++) {
			ac.label = i;
			ac.startTime = start[i];
			ac.finishTime = finish[i];
			activities.push_back(ac);
		}
		
	};*/
	void test(vector<Activity> &activities) {
		// 打印
		
		vector<int> result=greedyActivity(activities);
		cout << "最终安排结果是：" << endl;
		for (int i = 0; i < result.size();i++) {
			
			cout << result[i]<<" , ";
		}
	}


private:
	
	vector<int> greedyActivity(vector<Activity>& activities) {
		int j = 0;
		vector<int> solution = { 0 };
		for (int i = 1; i < activities.size();i++) {
			if (activities[i].startTime>= activities[j].finishTime) {
				solution.push_back(activities[i].label);
				j = i;
			}
		}
		return solution;
	}

};

bool cmp(const Activity& a, const Activity& b)//自定义结构体的排序,sort排序只能在main函数在调用
{
	return a.finishTime < b.finishTime;
}

int main() {
	vector<int> s = {1,3,0,5,3,5,6,8,8,2,12};
	vector<int> f = { 4,5,6,7,8,9,10,11,12,13,14 };
	vector<Activity> activities;
	for (int i = 0; i < 11; i++) {
		Activity ac = Activity();
		ac.label = i;
		ac.startTime = s[i];
		ac.finishTime = f[i];
		activities.push_back(ac);
	}
	Ques20201012 qus = Ques20201012();
	sort(activities.begin(), activities.end(), cmp); // 自定义结构体排序，vector排序

	qus.test(activities);
	return 0;
}

3. 贪心策略的证明

二、 背包问题

与上题类似，不过贪心策略是按单位价值，最后一个直接装一部分。

1. 代码

class Ques20201012Q2
{
public:
	

	void test(vector<Knapsack>& goods) {
		// 打印
		vector<int> result = greedyKnapsack(goods,50);
		cout << "最终安排结果是：" << endl;
		for (int i = 0; i < result.size(); i++) {

			cout << result[i] << " , ";
		}
	}


private:

	vector<int> greedyKnapsack(vector<Knapsack>& napsacks, float M) {//M是总重量
		vector<int> solution;// 解向量
		float remain = M;
		int i;
		for (i= 0; i < napsacks.size();i++) {
			if (napsacks[i].weight<= remain) {
				solution.push_back(napsacks[i].label);
				remain = remain - napsacks[i].weight;
			}
			else
			{
				break;
			}
		}
		if (i<= napsacks.size()) {
			float lastOne = remain / napsacks[i].weight;
			if (lastOne!=0) {
				solution.push_back(napsacks[i].label);
				cout << "最后一项装的是重量为:"<<lastOne<<endl;
			}
			
		}
		return solution;
	}
};

bool cmp2(const Knapsack& a, const Knapsack& b)//自定义结构体的排序,sort排序只能在main函数在调用
{
	return a.unitValue > b.unitValue; // 这是增序
}
int main() {

	// Q2 背包问题

	vector<int> w = { 10,20,30 };
	vector<int> v = { 60,100,120 };
	vector<Knapsack> napsacks;
	for (int i = 0; i < w.size(); i++) {
		Knapsack na = Knapsack(w[i], v[i]);
		na.label = i;
		napsacks.push_back(na);
	}
	Ques20201012Q2 kna = Ques20201012Q2();
	sort(napsacks.begin(), napsacks.end(), cmp2); // 自定义结构体排序，vector排序

	kna.test(napsacks);




	return 0;
}

2. 贪心证明