Question

完全背包问题，c语言编程

#include<stdio.h>
int V[1000][1000];int max(int a,int b){ if(a>=b) return a; else return b;}
int KnapSack(int n,int w[],int v[],int C){ int i,j; for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=C;j++) V[0][j]=0; for(i=0;i<=n-1;i++) for(j=0;j<=C;j++) if(j<w[i]) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]); j=C; for(i=n-1;i>=0;i--) if(V[i][j]>V[i-1][j]) j=j-w[i]; return V[n-1][C];}
int main(void){ int s; int w[1000]; int v[1000]; int n,i; int C; scanf("%d %d", &C, &n); for(i=0;i<n;i++) scanf("%d %d",&w[i], &v[i]); s=KnapSack(n,w,v,C); printf("%d",s);
return 0;}
这是我的源码，求大神找出我的错误，找不出来了

Answer 1

#include<stdio.h>
float V[1000],V1[1000];
int max(float a[],int n)
{
int s = 1;
float fmax = a[1];
for (int j=2;j<n;j++)
{
if (a[j]>fmax)
{
fmax = a[j];
a[j] = 0;
s = j;
}
}
return s;
}

int KnapSack(int n,int w[],int v[],int C)
{
int Maxvalue = 0;
int X[1000],w0[1000],w1[1000];
memset(X,0,sizeof(X));
memset(w0,0,sizeof(w0));
memset(w1,0,sizeof(w0));
for (int j=1;j<n;j++)
{
V[i] = 1.0*v[i]/w[i];
V1[i] =V[i];
}
X[1] = max(V1,n);
int w0[1] = n/w[X];
int w1[1] = n%w[X];
int k = 1;
while (w1[k++]!=0)
{
X[K] = max(V1,n);
w0[k] = w1[k]/w[Y];
w1[k] = w1[k]%w[Y];
}
for (int m=1;m<k;m++)
{
Maxvalue+=w0[m]*w[X[K]]*v[X[k];
}
return Maxvalue;

}
int main(void)
{
int s;
int w[1000];
int v[1000];
int n,i;
int C;
scanf("%d %d", &C, &n);
for(i=0;i<n;i++)
scanf("%d %d",&w[i], &v[i]);
s=KnapSack(n,w,v,C);
printf("%d",s);
return 0;
}

追问

亲，你这编译一下好多错误啊

追答

#include
#include
float V[1000],V1[1000];
int fmax(float a[],int n)
{
int s = 1;
float fmax = a[1];
for (int j=2;jfmax)
{
fmax = a[j];
s = j;
}
}
a[s] = 0;
return s;
}

int KnapSack(int n,int w[],int v[],int C)
{
int Maxvalue = 0;
int X[1000],w0[1000],w1[1000];
memset(X,0,sizeof(X));
memset(w0,0,sizeof(w0));
memset(w1,0,sizeof(w0));
for (int j=1;j<n;j++)
{
V[j] = 1.0*v[j]/w[j];
V1[j] =V[j];
}
X[1] = fmax(V1,n);
w0[1] = n/w[X[1]];
w1[1] = n%w[X[1]];
int k = 1;
while (w1[k++]!=0&&k<n)
{
X[k] = fmax(V1,n);
w0[k] = w1[k-1]/w[X[k]];
w1[k] = w1[k-1]%w[X[k]];
}
for (int m=1;m<k;m++)
{
Maxvalue+=w0[m]*w[X[m]]*v[X[m]];
}
return Maxvalue;

}
int main(void)
{
int s;
int w[1000];
int v[1000];
int n,i;
int C;
scanf("%d %d", &C, &n);
for(i=1;i<n;i++)
scanf("%d %d",&w[i], &v[i]);
s=KnapSack(n,w,v,C);
printf("%d",s);
return 0;
}

追问

提交上去之后是wrong answer，大神求救

追答

#include
#include
float V[1000],V1[1000];
int fmax(float a[],int n)
{
int s = 1;
float fmax = a[1];
for (int j=2;jfmax)
{
fmax = a[j];
s = j;
}
}
a[s] = 0;
return s;
}

int KnapSack(int n,int w[],int v[],int C)
{
int Maxvalue = 0;
int X[1000],w0[1000],w1[1000];
memset(X,0,sizeof(X));
memset(w0,0,sizeof(w0));
memset(w1,0,sizeof(w0));
for (int j=1;j<=n;j++)
{
V[j] = 1.0*v[j]/w[j];
V1[j] =V[j];
}
X[1] = fmax(V1,n);
w0[1] = C/w[X[1]];
w1[1] = C%w[X[1]];
int k = 1;
while (w1[k++]!=0&&k<=n)
{
X[k] = fmax(V1,n);
w0[k] = w1[k-1]/w[X[k]];
w1[k] = w1[k-1]%w[X[k]];
}
for (int m=1;m<k;m++)
{
Maxvalue+=w0[m]*w[X[m]]*v[X[m]];
}
return Maxvalue;

}
int main(void)
{
int s;
int w[1000];
int v[1000];
int n,i;
int C;
scanf("%d %d", &C, &n);
for(i=1;i<=n;i++)
scanf("%d %d",&w[i], &v[i]);
s=KnapSack(n,w,v,C);
printf("%d",s);
return 0;
}