运行没有错误,但是为什么我这个程序出不来结果呢。
#include <stdio.h>
#define C 100
int min(int a,int b)
{
if (a<=b)
return a;
else
return b;
}
int max(int a,int b)
{
if (a<=b)
return b;
else
return a;
}
void Knapsack(int* v,int *w,int c,int n,int (*m)[100])
{
int i,j;
int jMax=min(w[n]-1,c);
for (j=0;j<=jMax;j++)
m[n][j]=0;
for (j=w[n];j<=c;j++)
m[n][j]=v[n];
for (i=n-1;i>1;i--)
{
jMax=min(w[i]-1,c);
for (j=0;j<=jMax;j++)
m[i][j]=m[i+1][j];
for (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];
if (c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(int (*m)[100],int *w,int c,int n,int* x)
{
int i;
for (i=1;i<n;i++)
if (m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c])?1:0;
}
void main()
{
int i;
int w[10],v[10],x[10]={0,0,0,0,0,0,0,0,0,0};
int m[10][C];
printf("请输入10个物品的重量:\n");
for (i=0;i<10;i++)
scanf("%d",&w[i]);
printf("请输入10个物品的价值:\n");
for (i=0;i<10;i++)
scanf("%d",&v[i]);
Knapsack(v,w,C,10,m);
Traceback(m,w,C,10,x);
for (i=0;i<10;i++)
{
if (x[i]==0)
printf("第%d个物品不可放入",i);
if (x[i]==1)
printf("第%d个物品可放入",i);
}
}
#include <stdio.h>
#define C 100
int min(int a,int b)
{
if (a<=b)
return a;
else
return b;
}
int max(int a,int b)
{
if (a<=b)
return b;
else
return a;
}
void Knapsack(int* v,int *w,int c,int n,int (*m)[100])
{
int i,j;
int jMax=min(w[n]-1,c);
for (j=0;j<=jMax;j++)
m[n][j]=0;
for (j=w[n];j<=c;j++)
m[n][j]=v[n];
for (i=n-1;i>1;i--)
{
jMax=min(w[i]-1,c);
for (j=0;j<=jMax;j++)
m[i][j]=m[i+1][j];
for (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];
if (c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(int (*m)[100],int *w,int c,int n,int* x)
{
int i;
for (i=1;i<n;i++)
if (m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c])?1:0;
}
void main()
{
int i;
int w[10],v[10],x[10]={0,0,0,0,0,0,0,0,0,0};
int m[10][C];
printf("请输入10个物品的重量:\n");
for (i=0;i<10;i++)
scanf("%d",&w[i]);
printf("请输入10个物品的价值:\n");
for (i=0;i<10;i++)
scanf("%d",&v[i]);
Knapsack(v,w,C,10,m);
Traceback(m,w,C,10,x);
for (i=0;i<10;i++)
{
if (x[i]==0)
printf("第%d个物品不可放入",i);
if (x[i]==1)
printf("第%d个物品可放入",i);
}
}