项目规划算法题-C++实现_有一项大的工程,工程中有许多前后依赖的子任务,每个子任务都规划了完成需要的天数

前言

本文记录4月27日晚7点一场软件开发岗笔试的题目，思路以及代码实现。

一、题目简介

题目：
项目规划
具体描述：
公司做项目规划，当前三个团队（前端，后端，测试）共同规划完成M个项目，我们有三个团队的各自人力总和值。对于每个项目都需要多个团队共同投入完成（每个项目会有对3个项目的人力需求数量），每个项目会有一个预期价值。我们需要在M各项目中作项目规划，使得在人力允许的范围内，使能够承接的所有项目预期价值总和最大。
输入输出：
输入：
2
100 100 100
10000 8000
60 60 60
60 60 60
第一行表示有M=2个项目
第二行表示三个团队的各自人力总和
第三行表示M个项目各自的预期价值
第四行和第五行表示M=2个项目各自需要的三个团队人力需求量
输出：
10000
项目规划后预期可以获得的最大价值

二、思路

本题应该有简单的代码实现方法，我看这个题有点贪心那味，但想不出来具体怎么操作。那么我们先考虑其它方法，基于4月13日分糖果算法题得出的结论：要输出路径优先考虑DFS，只输出最优值优先考虑DP，那么本题应该优先考虑DP做法，即视为一个0-1背包问题处理，但是背包的体积会受到三个条件的约束，再加上还要枚举每个项目，所以相当于是一个四重循环的操作，细思极恐，如果要降维这又得折腾半天。因此我们最终决定使用DFS搜索算法来解决，思路非常简单：即依次枚举每个项目选或不选，每次把所有项目选不选的情况枚举完后更新最大价值即可。
不足：时间复杂度上可能存在问题，因为这个做法最坏情况下会达到O(2^n)的时间复杂度，本题中0<M<=20，有可能会超时。

三、C++代码实现

#include<iostream>
#include<vector>
using namespace std;
int m;
int front, rear, test;
int res = 0;

struct Team
{
	int front, rear, test;
}team;

struct Project
{
	int front, rear, test, value;
};

void dfs(Team team, vector<Project> f, int u, int value)
{
	if (u == m)
	{
		res = max(res, value);
		return;
	}
	if (team.front >= f[u].front && team.rear >= f[u].rear && team.test >= f[u].test)
	{
		team.front -= f[u].front;
		team.rear -= f[u].rear;
		team.test -= f[u].test;
		value += f[u].value;

		dfs(team, f, u + 1, value);

		value -= f[u].value;
		team.test += f[u].test;
		team.rear += f[u].rear;
		team.front += f[u].front;
	}
	dfs(team, f, u + 1, value);
}

int main()
{
	cin >> m;
	vector<Project> f(m);
	cin >> team.front >> team.rear >> team.test;
	for (int i = 0; i < m; i++) cin >> f[i].value;
	for (int i = 0; i < m; i++) cin >> f[i].front >> f[i].rear >> f[i].test;
	dfs(team, f, 0, 0);
	cout << res << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

总结

搜索算法是解决穷举遍历问题和最优化问题的一个必杀方法，虽然不能保证复杂度最低，但是一定能够解决。不过在做算法题的过程中不能只满足于实现要求，要尽力在困难复杂的问题中寻觅简单便捷的思路，将思路整理成套路，有了套路的积累才能在没有见过的新问题上产出新的想法，达到举一反三，指数爆炸的实力成长效果。
欢迎大佬提供更优的解法！