题目分析
本题是一个资源分配优化问题。公司有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≤10，k ≤ 10 k \leq 10k≤10。最坏情况下，如果直接枚举所有分配组合，总组合数为∏ i = 1 d ( n i × k i ) \prod_{i=1}^{d} (n_i \times k_i)∏i=1d(ni×ki)，最大可达( 10 × 10 ) 20 = 100 20 (10 \times 10)^{20} = 100^{20}(10×10)20=10020，显然不可行。
但由于资源总量有上限（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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intd,p,b,n,k;intoption[25][15][15],programmer[25][15],budget[25][15];intvisited[25],used[25][15][15];map<int,pair<int,int>>path,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_lines>max_code_lines){max_code_lines=current_code_lines;max_programmer=current_programmer;max_budget=current_budget;best.clear();for(autop:path)best.insert(p);}// 尝试为每个尚未分配的部门分配资源for(inti=1;i<=d;i++)if(visited[i]==0){visited[i]=1;// 遍历该部门的所有程序员选项和预算选项for(intx=1;x<=programmer[i][0];x++)for(inty=1;y<=budget[i][0];y++){// 跳过已使用的方案if(used[i][x][y]==1)continue;// 剪枝：超过总资源限制则跳过if(current_programmer+programmer[i][x]>p)continue;if(current_budget+budget[i][y]>b)continue;used[i][x][y]=1;path[i]=make_pair(x,y);dfs(current_programmer+programmer[i][x],current_budget+budget[i][y],current_code_lines+option[i][x][y]);path.erase(i);used[i][x][y]=0;}visited[i]=0;}}intmain(intargc,char*argv[]){intcases=0;while(cin>>d,d>0){cin>>p>>b;// 读取每个部门的数据for(inti=1;i<=d;i++){cin>>n;programmer[i][0]=n;// programmer[i][0]存储选项数量for(intj=1;j<=n;j++)cin>>programmer[i][j];cin>>k;budget[i][0]=k;// budget[i][0]存储选项数量for(intj=1;j<=k;j++)cin>>budget[i][j];// 读取n×k的增量代码行数表格for(intx=1;x<=n;x++)for(inty=1;y<=k;y++)cin>>option[i][x][y];}// 输出控制：两个测试用例之间打印两个空行if(cases)cout<<endl<<endl;cout<<"Optimal resource allocation problem #"<<++cases<<endl;// 初始化并执行搜索memset(visited,0,sizeof(visited));memset(used,0,sizeof(used));max_code_lines=0,max_programmer=0,max_budget=0;dfs(0,0,0);// 输出总结果cout<<endl;cout<<"Total budget: $"<<max_budget<<endl;cout<<"Total new programmers: "<<max_programmer<<endl;cout<<"Total productivity increase: "<<max_code_lines<<endl;// 输出每个部门的分配详情for(inti=1;i<=d;i++){cout<<endl;cout<<"Division #"<<i<<" resource allocation:"<<endl;cout<<"Budget: $"<<budget[i][best[i].second]<<endl;cout<<"Programmers: "<<programmer[i][best[i].first]<<endl;cout<<"Incremental lines of code: "<<option[i][best[i].first][best[i].second]<<endl;}}return0;}
