0-1背包的c语言程序运行结果总是出错,求指教
你没理解什么是0 1背包问题,要么背要么不背不能切分你这是部分背包问题的程序。
可以分析你结果是5的树据
2 3
2 2
3 4
程序先算价值得出第二个价值大是2第一个价值只有1.5
然后程序选择第二个,然后还剩下1kg选择背第一个的1kg可是可怕的事情来了,你int型数 1*2=2
你背了第一个物品1kg的那部分价值竟然为2
然后结果自然就是2+3=5;
由此可见你如果改成float型就是比较正确的求部分背包问题了。
而0 1背包问题是用动态规划算法而不是你现在的贪心。实际上0 1背包问题的动态规划还是有点难理解的。
C语言动态规划——0-1背包问题
以前写的 自己看吧
#include
int w[5]={0,3,5,2,1},p[5]={0,9,10,7,4};
int c=7,n=4;
int cw=0,cp=0,bestp=0;
int x[10]={0};
void try(int k)
{
int i;
if(k>n)
{
for(i=1;i<=n;i++)
printf("%2d",x[i]);
printf(" %d %d\n",cw,cp);
if(bestp<cp)
bestp=cp;
}
else
{
x[k]=1;
cw=cw+w[k];
cp=cp+p[k];
if(cw<=c)
try(k+1);
x[k]=0;
cw=cw-w[k];
cp=cp-p[k];
if(cw<=c)
try(k+1);
}
}
main()
{
clrscr();
try(1);
printf("best_P=%d",bestp);
}