五个人分别从事五项工作，求最佳安排使得效益最高(C++实现)
Problem：
文章图片
【五个人分别从事五项工作，求最佳安排使得效益最高(C++实现)】思路都在注释里面啦
Code：
#include
using namespace std;
//a[i][j]表示第i个人做第j项工作的效益
int a[][5] = {
10, 11, 10, 4, 7,
13, 10, 10, 8, 5,
5, 9, 7, 7, 4,
15, 12, 10, 11, 5,
10, 11, 8, 8, 4
};
// num[i] 对应当前第i个人选择方案的编号
// g[i] 对应最高效益的第i个人选择方案的编号
// maxv 对应最高效益和
// tmp用于存储 f 对应的当前效益和
// p[i] 用于表示第i项工作是否已分配，
int num[5], g[5], maxv, tmp;
bool p[5];
//check函数用于判断num数组当前方案是否比g数组的方案更优
bool check() {
tmp = 0;
for (int i = 0;
i < 5;
i++)// 因为分配给第i个人的工作编号是p[i]
tmp += a[i][num[i]];
// 所以tmp需要加上 a[i][ p[i] ]
return tmp > maxv;
}//用于更新 g 和 maxv
void update() {
maxv = tmp;
for (int i = 0;
i < 5;
i++)
g[i] = num[i];
}//dfs函数用于搜过第id个人对应的工作编号
void dfs(int id) {
if (id == 5) {// 5个人的工作都分配好了
if (check())// 如果当前方案比g数组的方案更好
update();
// 那么更新 g数组 和 最大效益和maxv
return;
}
for (int i = 0;
i < 5;
i++) {
if (p[i] == false) {// p[i]==false说明第i项工作还没有人做
num[id] = i;
// 尝试让第id个人做第i项工作
p[i] = true;
// 同时标记第i项工作已经有人做了
dfs(id + 1);
// 为第id+1个人分配工作
p[i] = false;
// 回溯回来后，将p[i]重置为false
}
}
}//output函数用于输出maxv和最高效益方案g
void output() {
cout <<"效益最高为："<< maxv << endl;
cout << "A、B、C、D、F分别完成：" << endl;
for (int i = 0;
i < 5;
i++)
cout << "J" << g[i] + 1 << "";
cout << endl;
}int main() {
dfs(0);
output();
system("pause");
return 0;
}
推荐阅读
- 一个人的旅行，三亚
- android第三方框架（五）ButterKnife
- 一个人的碎碎念
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- 七年之痒之后
- 异地恋中，逐渐适应一个人到底意味着什么（）
- 【故障公告】周五下午的一次突发故障
- 华为旁！大社区、地铁新盘，佳兆业城市广场五期！
- 遗憾是生活的常态，但孝顺这件事，我希望每一个人都不留遗憾
- NO.38|NO.38 我不是嫁不出去，而是不想嫁