公司出游 — 头疼的行政和财务
某公司计划十一集体出游！行政方面提出了一些出游计划，其中包含了N多项出游项目提供大家选择，
经过职员的意向统计之后得到一个列表，如下：
（注：优先级为职员统计之后的该项目的关注度，从1-9 标识 1最高）
活动项 金额 优先级
项目1 150 2
项目2 1000 3
项目3 250 1
项目4 820 4
项目5 450 2
项目6 180 5
项目7 335 4
项目8 530 7
项目9 485 4
项目10 295 3
项目11 630 8
项目12 769 4
项目13 389 3
现财务要求行政控制每人金额在3000-3500.项目数量控制在6-9（包含边界值） 行政开始头疼怎么去选择项目组合技能控制在限定金额内，又能让员工玩的好（即组合的优先级和值最低）。行政找你，你会怎么去设计？
步兵还是骑兵
12 years ago
Answers
能帮到行政妹妹的忙，程序猿哥哥太开心啦~~~
N 如果不大，可以直接暴力求出所有 6~9 个的组合。然后删选就好了。
#include <iostream>
#include <vector>
#include <cfloat>
struct Node
{
int cost;
int priority;
Node(const int _cost, const int _priority) : cost(_cost), priority(_priority) {}
};
// get com[binations] of k activities out of n activities. save the best combination into the result.
void combineHelper(std::vector<Node> &activities, std::vector<int> &com, std::vector<int> &result,
double &avgPri, const int &maxCost, const int &minCost,
int start, int index, const int &n, const int &k) {
if (index == k) {
double curAvgPri = 0;
int cost = 0;
for (int i = 0; i < com.size(); ++i) {
curAvgPri += activities[com[i]].priority;
cost += activities[com[i]].cost;
}
curAvgPri /= (double)k;
// get the result with lowest avg priority and proper cost
if (cost >= minCost && cost <= maxCost && curAvgPri < avgPri) {
for (int i = 0; i < com.size(); ++i) {
result[i] = com[i];
}
result[com.size()] = -1;
avgPri = curAvgPri;
}
return;
}
for (int i = start; i < n - k + index + 2; ++i) {
com[index] = i;
combineHelper(activities, com, result, avgPri, maxCost, minCost, i + 1, index + 1, n, k);
}
}
std::vector<int> bestSchedule(std::vector<Node> &activities,
const int &minCost, const int &maxCost,
const int &minLimit, const int &maxLimit) {
std::vector<int> best(maxLimit + 1, -1);
double minAvgPri = DBL_MAX;
// 6 ~ 9 combinations
for (int i = minLimit; i <= maxLimit; ++i) {
std::vector<int> com(i, 0);
combineHelper(activities, com, best, minAvgPri,
maxCost, minCost, 1, 0, activities.size(), i);
}
std::cout << "Best activity schedule includes: " << std::endl;
for (int i = 0; i < best.size(); ++i) {
if (best[i] == -1) break;
std::cout << "activity " << best[i] << std::endl;
}
return best;
}
int main(int argc, char const *argv[])
{
std::vector<Node> activities;
activities.push_back(Node(150, 2));
activities.push_back(Node(1000, 3));
activities.push_back(Node(250, 1));
activities.push_back(Node(820, 4));
activities.push_back(Node(450, 2));
activities.push_back(Node(180, 5));
activities.push_back(Node(335, 4));
activities.push_back(Node(530, 7));
activities.push_back(Node(485, 4));
activities.push_back(Node(295, 3));
activities.push_back(Node(630, 8));
activities.push_back(Node(769, 4));
activities.push_back(Node(389, 3));
std::vector<int> best = bestSchedule(activities, 3000, 3500, 6, 9);
return 0;
}
输出：
Best activity schedule includes:
activity 1
activity 2
activity 3
activity 4
activity 9
activity 12
activity 13
请吃饭哦？嘿嘿嘿
lanyuy
answered 12 years ago