而为数组动态内存分配成功了,但是在函数中用而为数组时出有关问题了
而为数组动态内存分配成功了,但是在函数中用而为数组时出问题了。
那个m[i][j]二维数组的内存应该是分配成功了的,但是在执行函数的时候就挂掉了~~
这个程序的功能是实现个0-1背包问题
------解决方案--------------------
那个m[i][j]二维数组的内存应该是分配成功了的,但是在执行函数的时候就挂掉了~~
这个程序的功能是实现个0-1背包问题
- C/C++ code
#include <stdio.h> #include <malloc.h> int min(int x,int y); int max(int x,int y); int **Knapack(int *v,int *w,int n,int c); int *Traceback(int **m,int *w,int c,int n); int main(void) { int c = 0; int n = 0; int *v = NULL; int *w = NULL; int **arr = NULL; int *x = NULL; printf("请输入背包的容量:"); scanf("%d",&c); getchar(); printf("请输入物品的个数:"); scanf("%d",&n); w = (int *)malloc(sizeof(int) * n); printf("请分别输入%d个物品的重量:",n); for(int i = 0; i < n; i++) scanf("%d",(w + i)); v = (int *)malloc(sizeof(int) * n); printf("请分别输入%d个物品的价值:",n); for(int i = 0; i < n; i++) scanf("%d",(v + i)); arr = Knapack(v,w,n,c); x = Traceback(arr,w,c,n); for (int i = 0; i < n; i++) { for (int j = 0; j < c; j++) { printf("%d ",arr[i][j]); } printf("\n"); } for(int i= 0; i < n; i++) { printf("%d ",x[i]); } printf("\n"); for (int i = 0; i < n; i++) { free(arr[i]); } free(arr); free(v); free(w); return 0; } int min(int x,int y) { if(x > y) return y; else return x; } int max(int x,int y) { if(x > y) return x; else return y; } int ** Knapack(int *v,int *w,int n,int c) { int **m = (int **)malloc(sizeof(int *) * n); for (int i = 0; i < n; i++) { m[i] = (int *)malloc(sizeof(int) * c); } // if (NULL == m) // { // printf("内存分配失败!"); // } int jMax = w[n-1] - 1; for(int j = 0; j <= jMax; j++) m[n ][j] = 0; /通过调试查出错误就在这/ for(int j = w[n-1]; j <= c; j++) m[n][j] = v[n-1]; for(int i = n - 1; i > 1; i--) { jMax = min(w[i] - 1,c); for(int j = 0; j <= jMax; j++) m[i][j] = m[i + 1][j]; for(int j = w[i]; j <= c; j++) m[i][j] = max(m[i + 1][j],m[i + 1][j - w[i]] + v[i]); } m[1][c - 1] = m[2][c - 1]; if(c >= w[1]) { m[1][c] = max(m[1][c],m[2][c - w[1]] + v[1]); } return m; } int *Traceback(int **m,int *w,int c,int n) { int *x = (int *)malloc(sizeof(int) * n); int i; for(i = 0; i < n; i++) { if (m[i][c - 1] == m[i + 1][c - 1]) x[i] = 0; else { x[i] = 1; c -= w[i]; } } x[n-1] = (m[n][c]) ? 1 : 0; return x; }
------解决方案--------------------
- C/C++ code
int **m = (int **)malloc(sizeof(int *) * n); for (int i = 0; i < n; i++) { m[i] = (int *)malloc(sizeof(int) * c); }
------解决方案--------------------
------解决方案--------------------
即使内存分配没有问题,你的下标还是可能溢出的
(二维指针,看的都有点晕)
int **m = (int **)malloc(sizeof(int *) * n);
m[i] = (int *)malloc(sizeof(int) * c);
也就是说,你的m[x][y]最大下标范围为
0<=x<=n-1
0<=y<=c-1
而你的程序中
for(int j = 0; j <= jMax; j++)
m[n ][j] = 0; //n已经有问题了,如果jMax>=c,下标肯定溢出
何况下面还有
for(int j = w[i]; j <= c; j++)
m[i][j] = max(m[i + 1][j],m[i + 1][j - w[i]] + v[i]);
下标也可能溢出的
我对二维指针应用头有点大,只能指出你的问题,自己或下面的高手改下吧