#include<stdio.h> #define MAXN 102 #define MAXM 102 //问题表示 int n; //部件数 int m; //供应商数 int cost; //限定价格 int w[MAXN][MAXM]; //w[i][j]为第i个零件在第j个供应商的重量 int c[MAXN][MAXM]; //c[i][j]为第i个零件在第j个供应商的价格 //求解结果表示 int bestx[MAXN]; int x[MAXN]; int cw=0,cc=0; int bestw=999999; bool find(int i,int j) //如果j在x[1..i-1]中出现，返回true，否则返回false { for (int k=1;k<i;k++) if (x[k]==j) return true; return false; } void dfs(int i) //求解算法 { /*补齐代码*/ } int main() { int i,j; scanf("%d%d%d",&n,&m,&cost); //输入部件数,供应商数,限定价格 for(i=1; i<=n; i++) //输入各部件的在不同供应商的重量 for(j=1; j<=m; j++) scanf("%d",&w[i][j]); for(i=1; i<=n; i++) //输入各部件的在不同供应商的价格 for(j=1; j<=m; j++) scanf("%d",&c[i][j]); dfs(1); //i从1开始搜索 for(i=1;i<=n;i++) //输出每个部件的供应商 printf("%d ",bestx[i]); printf("\n%d\n",bestw); //输出最小重量 return 0; }补全代码

以下是补全代码部分：

void dfs(int i) {
if(i>n) {
if(cw<=cost && cc<bestw) {
bestw=cc;
for(int j=1;j<=n;j++) bestx[j]=x[j];
}
return;
}
for(int j=1;j<=m;j++) {
if(find(i,j)) continue;
x[i]=j;
cw+=w[i][j];
cc+=c[i][j];
dfs(i+1);
cw-=w[i][j];
cc-=c[i][j];
}
}

首先判断是否搜索完所有部件，如果是，判断当前是否符合要求，并更新最小重量和最优解。如果未搜索完所有部件，就从所有供应商中选择一个，如果该供应商已经选过了就跳过，否则更新当前状态并进入下一层搜索。搜索完后，记得回溯状态。

相关问题

优化以下代码，使内存在64mb以内#include <stdio.h> #include <string.h> #include <limits.h> #define MAXN 2001 #define MAXK 2001 #define MAXM 10001 int n, k, m; int time[MAXN][MAXK]; int f[MAXN][MAXM]; int main() { scanf("%d%d%d", &n, &k, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { scanf("%d", &time[i][j]); } } for (int i = 0; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = 99999; } } f[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int x = 1; x <= k && x <= j; x++) { if (f[i-1][j-x] != 99999) { if (f[i][j] < f[i-1][j-x] + time[i][x]) f[i][j] = f[i][j]; else f[i][j] = f[i-1][j-x] + time[i][x]; } } } } printf("%d\n", f[n][m]); return 0; }

可以使用滚动数组进行优化，将二维数组f[n][m]转化为f[2][m]，每次只保留i和i-1的状态。同时，可以将time数组改为二维数组time[MAXK][MAXN]，这样在计算f[i][j]时可以直接使用time[x][i]，避免了内存的不必要占用。

另外，由于题目中规定m<=10000，因此可以将f数组的第二维缩小为10001，只保留必要的状态。

优化后的代码如下：

求一个给定的m×n矩阵各列元素之和。 输入格式： 输入第一行给出两个正整数m和n（1≤m,n≤6）。随后m行，每行给出n个整数，其间以空格分隔。 输出格式： 每行输出对应矩阵列元素之和。 输入样例： 3 2 6 3 1 -8 3 12 输出样例： 10 7 #include <stdio.h> #define MAXM 6 #define MAXN 6 int main() { int i, j, m, n, sum; int a[MAXM][MAXN]; scanf("%d %d", &m, &n); for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } for { for { sum += a[i][j]; } printf("%d\n", sum); } return 0; }

这道题目的思路是先读入矩阵，然后对每一列求和并输出。代码如下：

#include <stdio.h>

#define MAXM 6
#define MAXN 6

int main() {
    int i, j, m, n, sum;
    int a[MAXM][MAXN];

    scanf("%d %d", &m, &n);

    // 读入矩阵
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    // 对每一列求和并输出
    for (j = 0; j < n; j++) {
        sum = 0;
        for (i = 0; i < m; i++) {
            sum += a[i][j];
        }
        printf("%d ", sum);
    }
    printf("\n");

    return 0;
}

需要注意的是，在对每一列求和时，需要将 `sum` 初始化为 0。