注册 登录
编程论坛 C++教室

[求助]背包算法出错

yqfang310 发布于 2006-12-13 18:27, 651 次点击

#include<iostream.h>


int KnapSack(int s[], int v[], int n, int c);

void main()
{
int n =4;
int c =9;
int ret;
int s[] = {2,3,4,5};
int v[] = {3,4,5,7};
ret = KnapSack(s, v, n+1, c+1);
cout<<ret<<endl;
}

int KnapSack(int s[], int v[], int n, int c)
{
int i, j;
int **V;
V = new int*[n];
for (i=0; i<n; i++)
V[i] = new int[c]; //定义一个二维动态整形数组

for(i=0; i<n; i++) //初始化第一行和第一列第个元素的值为0
V[i][0] = 0;
for(j=0; j<c; j++)
V[0][j] = 0;

for(i=1; i<n; i++)
for(j=1; j<c; j++)
{
if((i>0) && (j<s[i]))
V[i][j] = V[i-1][j];


if(s[i] <= j)//当s[i] <= j时,找出V[i][j]和V[i-1][j-s[i]] + v[i]里比较大的值
{
if(V[i][j] >= (V[i-1][j-s[i]] + v[i]))
V[i][j] = V[i-1][j-s[i]] + v[i];
else
V[i][j] = V[i][j];
}
}

return V[n][c];

}

5 回复
#2
yqfang3102006-12-13 21:00
怎么没人理我啊
#3
smartwind2006-12-15 21:35

数组没有初始化

#4
yqfang3102006-12-15 22:35

拜托,这是动态二维数组好不好

#5
showna2006-12-15 22:58

for(i=1; i<n; i++)

if(s[i] <= j)//当s[i] <= j时,找出V[i][j]和V[i-1][j-s[i]] + v[i]里比较大的值

int s[] = {2,3,4,5};

n=5,s[4]的时候数组越界了

#6
yqfang3102006-12-17 14:11
你再仔细看一下
1