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背包问题怎么修改

0/1背包问题的目标是在限定的背包容量内，选择一定数量的物品，使得它们的总价值最大。这个问题可以使用动态规划算法求解，而上述代码就是一个求解0/1背包问题的动态规划算法。

在上述代码中，如果$x-w[i]\leqslant 0$，则表示当前物品$i$的重量已经超出了背包容量$x$，因此不能选取该物品。这个判断条件是错误的，因为当前物品的重量可能小于或等于背包容量$x$，但是在前面的物品中已经选取了一些物品，使得剩余容量不足以放入当前物品。

正确的判断条件是：如果$x-w[i]<0$，则表示当前物品$i$的重量已经超出了背包容量$x$，因此不能选取该物品。

此外，代码中缺少返回值，应该将计算得到的最大总价值返回。

修改后的代码如下：

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;
    }
}

相关问题

/* 第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w 第3行是各物品的价值p ，背包容量和物品重量都为整数。 */ #include<stdio.h> #include<string.h> int chose[9000]; int max(int a,int b){ if(a>=b) return a; else return b; } int price=0; int weight=0; 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; } } int main(){ //input int M,n; scanf("%d %d",&M,&n); int w[n+1]; int p[n+1]; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) scanf("%d",&p[i]); int ans=fb(n,M,w,p); printf("%d\n",ans); for(int i=1;i<=n;i++){ printf("%d ",chose[i]); } return 0; }为什么chose[2]是1

在您提供的代码中，选择一个物品的条件是：

if(choose>=not_choose){
    chose[i]=0;
    return choose;
}
else{
    chose[i]=1;
    return not_choose;
}

其中，如果选择第 $i$ 件物品，就将 `chose[i]` 赋值为1，否则赋值为0。

因为在递归调用 `fb` 函数时，物品的编号 $i$ 是递减的，所以最后得到的 `chose` 数组是倒序的。在您提供的数据中，第二件物品的重量为3，价值为2，如果将其放入背包，则剩余容量为3，还可以放入第三件物品。

因此，在第二次调用 `fb` 函数时，有：

choose = fb(1, 3, w, p) = 0
not_choose = fb(1, 0, w, p) + p[2] = 0 + 2 = 2

因为 `not_choose` 大于 `choose`，所以第二件物品被选择，即 `chose[2]` 被赋值为1。

所以，`chose` 数组中的第二个元素是1。

/* 第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w 第3行是各物品的价值p ，背包容量和物品重量都为整数。 */ #include<stdio.h> #include<string.h> int chose[9000]; int max(int a,int b){ if(a>=b) return a; else return b; } int price=0; int weight=0; int fb(int i,int x,int w[],int p[]){ if(i==0) return 0; if(x<0) return -999999999; 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]=1; return choose; } else{ chose[i]=0; return not_choose; } } int main(){ //input int M,n; scanf("%d %d",&M,&n); int w[n+1]; int p[n+1]; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) scanf("%d",&p[i]); int ans=fb(n,M,w,p); printf("%d\n",ans); for(int i=1;i<=n;i++){ printf("%d ",chose[i]); } return 0; }

这是一个背包问题的C语言实现，使用了递归的做法。程序会先读入背包容量M和物品数量n，然后读入每个物品的重量和价值。接着调用递归函数fb来计算能够放入背包中的物品的最大价值。

递归函数fb的参数i表示当前处理到第i个物品，x表示当前背包剩余的容量，w和p数组分别表示物品的重量和价值。函数会先判断是否已经处理完了所有物品（i==0），如果是则返回0。如果当前背包容量已经不足以放下当前物品，则不选当前物品，直接返回一个极小的负数（-999999999）。否则，递归地考虑选择当前物品和不选择当前物品两种情况，取两者中价值更大的一种。同时，记录下选择与否的情况，以便输出解。

程序最后输出最大价值以及选择的物品情况。