#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];

}

由上往下推，并不是由下往上推；
[CODE]v(i,j) = max{ v(i+1,j), v(i+1,j-wi)+vi} j>=wi
v(i+1,j) 0<=j<wi[/CODE]


其实，不必开二维数组，一维就够了．
[CODE]v[0-c]=0;
for (i=1; i<=n; i++)
{
for (j=c; j>=wi; j--)
{
d[j] = max(d[j],d[j-wi]+vi);
}
} [/CODE]
不断翻滚数组就够了。

什么意思啊，能不能帮我改一下我的程序啊

没听过背包问题

不是吧，那只能证明你不是学计算机的，难道这论坛就没人能帮我了吗

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

给个参考程序,LZ自己改下,程序是倒着判断是否可以放入的,即从n开始.
void Knapsack(int *v,int *w ,int c,int n,int **w)//v,表示价值w重量,c最大量,n,货物个数m(i,j)存放i到j的最优值.
{
int jMax=min(w[n]-1,c);
for(int j=0;j<=jMax;j++)
{
m[n][j]=0;
}
for(int j=w[n];j<=c;j++)
{
m[n][j]=v[n];
}

for(int i=n-1;i>1;i--)
{
jMax=min(w[i]-2,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]=m[2][c];//不把1放入
if(c>=w[1])//把1放进去
{
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
}

为什么会错呢？你说的那个地方，首行和首列不是要初始化为零的吗