int fb(int i,int x,int w[],int p[]){ if(i==0)return 0; if(x-w[i]<=0) return -999999999; if(fb(i-1,x,w,p)>fb(i-1,x-w[i],w,p)+p[i]) chose[i]=0;//没要 else { chose[i]=1; weight=weight+w[i]; price=price+p[i]; } } 0/1背包问题怎么修改
时间: 2024-03-12 14:48:03 浏览: 67
0/1背包问题
0/1背包问题的目标是在限定的背包容量内,选择一定数量的物品,使得它们的总价值最大。这个问题可以使用动态规划算法求解,而上述代码就是一个求解0/1背包问题的动态规划算法。
在上述代码中,如果$x-w[i]\leqslant 0$,则表示当前物品$i$的重量已经超出了背包容量$x$,因此不能选取该物品。这个判断条件是错误的,因为当前物品的重量可能小于或等于背包容量$x$,但是在前面的物品中已经选取了一些物品,使得剩余容量不足以放入当前物品。
正确的判断条件是:如果$x-w[i]<0$,则表示当前物品$i$的重量已经超出了背包容量$x$,因此不能选取该物品。
此外,代码中缺少返回值,应该将计算得到的最大总价值返回。
修改后的代码如下:
```c++
int fb(int i,int x,int w[],int p[]){
if(i==0) return 0;
if(x-w[i]<0) return fb(i-1,x,w,p);
int choose=fb(i-1,x,w,p);
int not_choose=fb(i-1,x-w[i],w,p)+p[i];
if(choose>=not_choose){
chose[i]=0;
return choose;
}
else{
chose[i]=1;
return not_choose;
}
}
```
阅读全文