求解最小机器重量设计2

1.采用回溯法求解

#include<bits/stdc++.h>
#define MAXN 102
#define MAXM 102
using namespace std;
int n,m,cost;
int w[MAXN][MAXM];
int c[MAXN][MAXM];
int bestx[MAXN];
int x[MAXN];
int cw=0,cc=0;
int bestw=9999;
bool find(int i,int j){
for(int k=1;k<i;k++){
if(x[k]==j) return true;
}
return false;
}
void dfs(int i){
if(i>n){
if(cw<bestw){
bestw=cw;
for(int j=1;j<=n;j++){
bestx[j]=x[j];
}
}
}else {
for(int j=1;j<=m;j++){
if(find(i,j)){
continue;
}
if(cc+c[i][j]<=cost&&cw+w[i][j]<=bestw){
x[i]=j;
cc+=c[i][j];
cw+=w[i][j];
dfs(i+1);
cc-=c[i][j];
cw-=w[i][j];
}
}
}
}
int main(){
cin>>n>>m>>cost;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
dfs(1);
for(int i=1;i<=n;i++){
cout<<bestx[i]<<" ";
}
cout<<endl<<bestw<<endl;
}

2.采用优先队列式分支限界法求解

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 10
#define MAXM 10
using namespace std;
int n,m,cost;
int w[MAXN][MAXN];
int c[MAXN][MAXN];
typedef struct {
int no,i,w,c;
int x[MAXN];
int y[MAXN];
}NodeType;
struct Cmp{
bool operator()(const NodeType &s,const NodeType &t){
return (s.w>t.w)||(s.w==t.w&&s.c>t.c);
}
};
int bestw=INF;
int bestc=INF;
int bestx[MAXN];
int Count=1;
void solve(){
NodeType e,e1;
priority_queue<NodeType,vector<NodeType>,Cmp> qu;
e.no=Count++;
e.i=0;e.w=0;e.c=0;
memset(e.x,0,sizeof(e.x));
memset(e.y,0,sizeof(e.y));
qu.push(e);
while(!qu.empty()){
e=qu.top();qu.pop();
if(e.i==n){
}else {
for(int j=1;j<=m;j++){
if(e.y[j]==0){
if(e.c+c[e.i+1][j]<=cost&&
e.c+c[e.i+1][j]<bestc&&e.w+w[e.i+1][j]<bestw){
e1.no=Count++;
e1.i=e.i+1;
e1.w=e.w+w[e1.i][j];
e1.c=e.c+c[e1.i][j];
for(int k=0;k<=n;k++) e1.x[k]=e.x[k];
for(int k=0;k<=n;k++) e1.y[k]=e.y[k];
e1.x[e1.i]=j;
e1.y[j]=1;
qu.push(e1);
}
}
}
}
}
}
int main(){
cin>>n>>m>>cost;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
solve();
for(int i=1;i<=n;i++){
cout<<bestx[i]<<" ";
}
cout<<endl<<bestw<<endl;
}

最后

以上就是天真口红为你收集整理的求解最小机器重量设计2的全部内容，希望文章能够帮你解决求解最小机器重量设计2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。