求解最小机器重量设计问题：一类最简单的深度优先搜索（BFS）策略
求解最小机器重量设计问题
题目内容：
设某一机器由n个部件组成,部件编号为1,2,…,n,每一种部件都可以从m个不同的供应商处购得，供应商编号为1~m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。（注意：输出结果中第一行最后没有空格。比如下面的输出样例中1 3 1后面没有空格。）
输入格式:
第1行输入3个正整数n,m和d。接下来n行输入wij（每行m个整数），最后n行输入cij（每行m个整数）,这里1≤n、m≤100。
输出格式：
输出的第1行包括n个整数，表示每个对应的供应商编号，第2行为对应的最小重量。
输入样例：
3 3 7
1 2 3
3 2 1
2 3 2
1 2 3
5 4 2
2 1 2
输出样例：
1 3 1
4
话不多说，先上一个可以A的C++代码（写的有点粗糙，见谅）：
#include<iostream>
using namespace std;
void solve(int m,int n,int d,int**w,int **c);
int main(){
int m=0,n=0,d=0;
int i=0,j=0;
cin>>n>>m>>d; //输入n,m,d
int **w=new int*[n+1];
w[0]=new int[(n+1)*(m+1)];
for(i=1;i<n+1;i++)
w[i]=w[i-1]+(m+1);
int **c=new int*[n+1];
c[0]=new int[(n+1)*(m+1)];
for(i=1;i<n+1;i++)
c[i]=c[i-1]+(m+1); //动态二维数组 w[][] 和c[][];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>w[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>c[i][j]; //输入w[][] 和 c[][];为了方便，没有使用下标出现0的位置；
solve(m,n,d,w,c); //解决问题
delete []c[0];
delete []c;
delete []w[0];
delete []w; //释放分配的内存空间
return 0;
}
void solve(int m,int n,int d,int**w,int **c){
int *x=new int[n+1]; //存储遍历的中间结果：x[i]∈{1,2,...,m} i∈{1,2,...,n}
int *ans=new int[n+1]; //存储问题的最终答案用于输出：ans[i]∈{1,2,...,m}
for(int i=0;i<=n;i++) x[i]=0;
for(int i=0;i<=n;i++) ans[i]=-1;//初始化
int k=1;
while(k>=1){
x[k]=x[k]+1;
while(x[k]<=m){
int cs=0;
for(int i=1;i<=k;i++)
cs=cs+c[i][x[i]];
if(cs<=d) break;
else x[k]=x[k]+1;
};
if(x[k]<=m&&k==n){
int ds=0;
for(int i=1;i<=n;i++)
ds=ds+w[i][x[i]];
if(ans[0]==-1||ds<ans[0]){
ans[0]=ds;
for(int i=1;i<=n;i++)
ans[i]=x[i];
}
continue;
}
if(k==1&&x[k]==m+1){
for(int i=1;i<=n-1;i++)
cout<<ans[i]<<" ";
cout<<ans[n]<<endl;
cout<<ans[0]<<endl;
return;
}
if(x[k]<=m&&k<n){
k++;
}else{
x[k--]=0;
}
}
}
看代码看得一脸懵？好吧，下面详细解释一下代码是怎么写出来的。
首先，在这个问题中使用了深度优先策略，不认识深度优先策略的自行去看讲数据结构的书，在树的遍历那一节。
我们从一道最简单的问题出发，探究深度优先策略怎么用：
用 A，B，C这三个字母填编号为 1,2,3,4的四个格子，字母可以重复使用，打印所有的填法。
显然，有3X3X3X3=81种不同的填法，因为第一号格子有A，B，C这三个选择，由于可以重复使用字母，当第一号格子填好后，第二号格子依然有三个选择，以此类推，答案就是3X3X3X3=81种不同的填法。
把这个问题一般化：用 m个不同的字母填编号为 1,2,…,n的n个格子，字母可以重复使用，打印所有的填法。
我把这个问题命名为 “填n格问题”，显然， “填n格问题”的解是 m^n种，现在的问题是怎么打印出来。
取m=2;n=3,我们可以画出下面这颗树：
其中节点编号为遍历顺序，不同的分枝为不同的选择，由于深度优先遍历是一个递归的过程，我们可以写出一个递归算法打印各种填格子的方式：
注意格子的编号 k=0,1,2,…,n-1;
#include<iostream>
using namespace std;
int n;
int m;
char w[]="ABCD";
char x[1000]; //保存填格子的中间结果
void solve(int k);
int main(){
n=3;
m=2;
solve(0);
return 0;
}
void solve(int k){
if(k==n){
for(int i=0;i<n;i++)cout<<x[i]<<" ";
cout<<endl;
return;
} //递归终止并打印
for(int i=0;i<m;i++){ //这个循环表示第k号格子有m种选择
x[k]=w[i]; //填第k号格子
solve(k+1); //填第k+1号格子
}
}
输出结果是
A A A
A A B
A B A
A B B
B A A
B A B
B B A
B B B
是不是特别简单，记住递归的基本套路：“如何终止”+“我调用我自己”。
众所周知，递归函数实际上是基于栈实现的，我们可以使用栈这种数据结构把一些简单的递归函数改写成非递归函数，比如我们可以把这段代码用栈改写成非递归算法：
这个算法实际上就是打印了完全m叉树，并且把每一条从根节点到叶子节点的路径都打印出来了，对于更多的问题，不是每一条路径都是问题的解。这个时候我们需要在遍历的时候遵循某些原则，依照这些原则忽略那些我们不需要的路径，这就是“剪枝”，这些原则就是剪枝函数。
我们来看下一个问题：打印n个不同的字母的全排列。
这个问题可以化归为“填n格问题”+“剪枝”：
“用 n个不同的字母填编号为 1,2,…,n的n个格子，打印所有的填法。”+“每个字母只能用一次”
#include<iostream>
using namespace std;
int n;
int m;
char w[]="ABCD";
char x[1000]; //保存填格子的中间结果
void solve(int k);
int main(){
n=4;
m=n;
solve(0);
return 0;
}
void solve(int k){
if(k==n){
for(int i=0;i<n;i++)cout<<x[i]<<" ";
cout<<endl;
return;
} //递归终止并打印
for(int i=0;i<m;i++){ //虽然这个循环表示第k号格子有m==n种选择,
bool flag=1;
for(int j=0;j<=k-1;j++)
if(x[j]==w[i]) flag=0;
if(flag){ //但是只有没被填过的字母才配填第k号格子
x[k]=w[i]; //填第k号格子
solve(k+1); //填第k+1号格子
}
}
}
输出
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D
B C D A
B D A C
B D C A
C A B D
C A D B
C B A D
C B D A
C D A B
C D B A
D A B C
D A C B
D B A C
D B C A
D C A B
D C B A
这里的代码块：
bool flag=1;
for(int j=0;j<=k-1;j++)
if(x[j]==w[i]) flag=0;
if(flag){
//*********
}
起到了“剪枝 ”的作用。