题目分析本题是一个资源分配优化问题。公司有d dd个编程部门愿意招聘最多p pp名新程序员并投入最多b bb美元预算用于硬件和软件系统。每个部门对于新资源的利用能力有限只有特定的几种有效分配方案。对于每个部门给定若干种程序员分配选项和预算分配选项的组合以及每种组合对应的预期代码行数增量。目标是决定每个部门分配多少新程序员和预算使得总代码行数增量最大且总程序员数不超过p pp总预算不超过b bb。输入包含多个测试用例每个用例的格式为第一行d , p , b d, p, bd,p,b接下来每个部门一行或多行首先给出程序员选项数量n nn然后是n nn个程序员数量接着给出预算选项数量k kk然后是k kk个预算金额最后是一个n × k n \times kn×k的表格表示每种组合的代码行数增量。输出需要给出最优分配方案的总预算、总程序员数、总代码行数增量以及每个部门的具体分配。解题思路本题数据范围较小d ≤ 20 d \leq 20d≤20每个部门的选项数n ≤ 10 n \leq 10n≤10k ≤ 10 k \leq 10k≤10。最坏情况下如果直接枚举所有分配组合总组合数为∏ i 1 d ( n i × k i ) \prod_{i1}^{d} (n_i \times k_i)∏i1d(ni×ki)最大可达( 10 × 10 ) 20 100 20 (10 \times 10)^{20} 100^{20}(10×10)2010020显然不可行。但由于资源总量有上限p pp和b bb考虑使用深度优先搜索DFS \texttt{DFS}DFS进行剪枝搜索。算法思路如下对每个部门记录其所有可能的程序员分配数量、预算金额及对应的代码行数。使用DFS \texttt{DFS}DFS递归处理每个部门在每一层尝试该部门所有可能的分配方案。递归过程中维护当前已分配的总程序员数、总预算和总代码行数。如果当前总程序员数超过p pp或总预算超过b bb则剪枝跳过。当所有部门处理完毕后更新全局最优解。使用visited数组标记部门是否已处理used数组防止同一部门的同一方案被重复使用实际上由于部门只处理一次这个标记可以省略但保留以保持代码完整性。由于每个部门最多有100 100100种方案d ≤ 20 d \leq 20d≤20最坏情况下搜索树规模为100 20 100^{20}10020但实际剪枝后会大大减少。由于p pp和b bb较小许多分支会被提前剪枝。在输出时注意不同测试用例之间有两个空行每个部门之间有一个空行。代码实现// Resource Allocation// UVa ID: 228// Verdict: Accepted// Submission Date: 2016-06-18// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intd,p,b,n,k;intoption[25][15][15],programmer[25][15],budget[25][15];intvisited[25],used[25][15][15];mapint,pairint,intpath,best;// path存储当前搜索路径best存储最优方案intmax_code_lines,max_programmer,max_budget;// 深度优先搜索// current_programmer: 当前已分配的总程序员数// current_budget: 当前已分配的总预算// current_code_lines: 当前已获得的总代码行数voiddfs(intcurrent_programmer,intcurrent_budget,intcurrent_code_lines){// 如果当前方案优于已知最优解则更新最优解if(current_code_linesmax_code_lines){max_code_linescurrent_code_lines;max_programmercurrent_programmer;max_budgetcurrent_budget;best.clear();for(autop:path)best.insert(p);}// 尝试为每个尚未分配的部门分配资源for(inti1;id;i)if(visited[i]0){visited[i]1;// 遍历该部门的所有程序员选项和预算选项for(intx1;xprogrammer[i][0];x)for(inty1;ybudget[i][0];y){// 跳过已使用的方案if(used[i][x][y]1)continue;// 剪枝超过总资源限制则跳过if(current_programmerprogrammer[i][x]p)continue;if(current_budgetbudget[i][y]b)continue;used[i][x][y]1;path[i]make_pair(x,y);dfs(current_programmerprogrammer[i][x],current_budgetbudget[i][y],current_code_linesoption[i][x][y]);path.erase(i);used[i][x][y]0;}visited[i]0;}}intmain(intargc,char*argv[]){intcases0;while(cind,d0){cinpb;// 读取每个部门的数据for(inti1;id;i){cinn;programmer[i][0]n;// programmer[i][0]存储选项数量for(intj1;jn;j)cinprogrammer[i][j];cink;budget[i][0]k;// budget[i][0]存储选项数量for(intj1;jk;j)cinbudget[i][j];// 读取n×k的增量代码行数表格for(intx1;xn;x)for(inty1;yk;y)cinoption[i][x][y];}// 输出控制两个测试用例之间打印两个空行if(cases)coutendlendl;coutOptimal resource allocation problem #casesendl;// 初始化并执行搜索memset(visited,0,sizeof(visited));memset(used,0,sizeof(used));max_code_lines0,max_programmer0,max_budget0;dfs(0,0,0);// 输出总结果coutendl;coutTotal budget: $max_budgetendl;coutTotal new programmers: max_programmerendl;coutTotal productivity increase: max_code_linesendl;// 输出每个部门的分配详情for(inti1;id;i){coutendl;coutDivision #i resource allocation:endl;coutBudget: $budget[i][best[i].second]endl;coutProgrammers: programmer[i][best[i].first]endl;coutIncremental lines of code: option[i][best[i].first][best[i].second]endl;}}return0;}
