#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; } Dfs(int i)函数的完成代码如下: void dfs(int i) //求解算法 { /*补齐代码*/ }
时间: 2024-04-02 20:36:12 浏览: 57
void dfs(int i) {
if (i > n) { //搜索到第n+1个部件,更新最优解
if (cw < bestw) {
bestw = cw;
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
}
return;
}
for (int j = 1; j <= m; j++) { //枚举第i个部件的供应商
if (c[i][j] <= cost && !find(i, j)) { //价格不超过限定价格且该供应商未选择过
x[i] = j;
cc += c[i][j];
cw += w[i][j];
dfs(i + 1);
cc -= c[i][j];
cw -= w[i][j];
x[i] = 0;
}
}
}
相关问题
优化以下代码,使内存在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。
阅读全文