# 最小重量机器设计问题

``````3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
``````

``````4
1 3 1``````

``````
#include<stdio.h>

#define INF 999999999

int w[22][22];
int c[22][22];
int v[22], s[22];
int m, n, d;
int min, minw, maxc;

void DFS( int t, int p, int cnt ){
int i;
if( t > n ){
if( cnt < min ){
min = cnt;
for( int i=1; i<=m; i++ )
s[i] = v[i];
}
return ;
}
if( cnt > min || d < p ){
return ;
}
for( i=1; i<=m; i++ ){
if( d >= p + c[t][i] ){
v[t] = i;
DFS( t+1, p+c[t][i], cnt+w[t][i] );
}
}
}

int main(){
int i, j;
int tmp, r;
while( scanf( "%d%d%d", &n, &m, &d ) != EOF ){
maxc = minw = 0;
for( i=1; i<=n; i++ ){
for( j=1; j<=m; j++ ){
scanf( "%d", &c[i][j] );
if( j == 1 ) { tmp = c[i][j]; }
else if( tmp < c[i][j] )  { tmp = c[i][j]; }
}
maxc += tmp;
}
for( i=1; i<=n; i++ ){
for( j=1; j<=m; j++ ){
scanf( "%d", &w[i][j] );
if( j == 1 ) { tmp = c[i][j]; r = j; }
else if( tmp > c[i][j] )  { tmp = c[i][j]; r = j; }
}
minw += tmp;
s[i] = r;
}
if( maxc < d ){
printf( "%d\n", minw );
for( i=1; i<n; i++ )
printf( "%d ", s[i] );
printf( "%d", s[i] );
continue;
}
min = INF;
DFS( 1, 0, 0 );
printf( "%d\n", min );
for( i=1; i<n; i++ )
printf( "%d ", s[i] );
printf( "%d", s[i] );
}
return 0;
}
``````

``````
#include<stdio.h>

#define INF 999999999

int w[22][22];
int c[22][22];
int v[22], s[22];
int m, n, d;
int min, minw, maxc;

void DFS( int t, int p, int cnt ){
int i;
if( t > n ){
if( cnt < min ){
min = cnt;
for( int i=1; i<=m; i++ )
s[i] = v[i];
}
return ;
}
if( cnt > min || d < p ){
return ;
}
for( i=1; i<=m; i++ ){
if( d >= p + c[t][i] ){
v[t] = i;
DFS( t+1, p+c[t][i], cnt+w[t][i] );
}
}
}

int main(){
int i, j;
int tmp, r;
while( scanf( "%d%d%d", &n, &m, &d ) != EOF ){
maxc = minw = 0;
for( i=1; i<=n; i++ ){
for( j=1; j<=m; j++ ){
scanf( "%d", &c[i][j] );
if( j == 1 ) { tmp = c[i][j]; }
else if( tmp < c[i][j] )  { tmp = c[i][j]; }
}
maxc += tmp;
}
for( i=1; i<=n; i++ ){
for( j=1; j<=m; j++ ){
scanf( "%d", &w[i][j] );
if( j == 1 ) { tmp = c[i][j]; r = j; }
else if( tmp > c[i][j] )  { tmp = c[i][j]; r = j; }
}
minw += tmp;
s[i] = r;
}
if( maxc < d ){
printf( "%d\n", minw );
for( i=1; i<n; i++ )
printf( "%d ", s[i] );
printf( "%d", s[i] );
continue;
}
min = INF;
DFS( 1, 0, 0 );
printf( "%d\n", min );
for( i=1; i<n; i++ )
printf( "%d ", s[i] );
printf( "%d", s[i] );
}
return 0;
}
``````