/* 第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 f[n+1][M+1]={0}; int w[M+1]; int p[M+1]; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<=n;i++)printf("%d ",chose[i]); }为什么6 3 2 3 4 1 2 5chose数组里面全是0.

在您提供的代码中，虽然您已经调用了函数 `fb` 来计算背包问题的最优解，但是您并没有将最优解记录下来，而是直接输出了 `chose` 数组。因此，`chose` 数组的值一直为初始值0。

要解决这个问题，您需要在调用函数 `fb` 后，将最优解记录下来，然后再输出 `chose` 数组。可以将最优解保存在变量 `ans` 中，然后根据 `chose` 数组的定义，倒序输出选取的物品，代码如下：

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=n;i>=1;i--){
        if(chose[i]==1){
            printf("%d ",i);
        }
    }
    return 0;
}

这样，就可以正确输出背包问题的最优解和选取的物品了。

相关问题

动态规划解决0/1背包问题的C++代码，满足如下条件：输入格式: 第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w i ​ ； 第3行是各物品的价值p i ​ ，背包容量和物品重量都为整数。 输出格式: 第1行是所选物品的价值之和，以及重量之和； 第2行是各物品装入背包的量，即x i ​ 值。

以下是符合要求的C++代码，解决0/1背包问题：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1005;

int M, n;
int w[MAXN], p[MAXN];
int f[MAXN][MAXN], x[MAXN];

int main() {
    cin >> M >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= M; j++) {
            if (j >= w[i]) {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + p[i]);
            } else {
                f[i][j] = f[i - 1][j];
            }
        }
    }
    cout << f[n][M] << " ";
    int v = M;
    for (int i = n; i >= 1; i--) {
        if (f[i][v] == f[i - 1][v]) {
            x[i] = 0;
        } else {
            x[i] = 1;
            v -= w[i];
        }
    }
    cout << M - v << endl;
    for (int i = 1; i <= n; i++) {
        cout << x[i] * (M - v) << " ";
    }
    cout << endl;
    return 0;
}

该代码使用二维数组f[i][j]表示前i件物品放入容量为j的背包中所能获得的最大价值，其中f[i][j]的值为：

- 若j >= w[i]，则f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + p[i])，即第i件物品放入背包中与不放入背包中所能获得的最大价值的较大值；
- 若j < w[i]，则f[i][j] = f[i - 1][j]，即第i件物品放不下，只能选择不放。

最终输出选取的物品的总价值和总重量以及每个物品装入背包的量。

给出N物品和背包的容量M，第i件物品的容量为ai，价值为bi，假设物品可以切割，求能装进背包的最大价值

这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。

初始化时，dp[0][j] = 0，表示前0个物品放入任何容量的背包中所能获得的最大价值都为0；dp[i][0] = 0，表示容量为0的背包中放入任何物品所能获得的最大价值都为0。

然后，我们可以使用以下状态转移方程来更新dp数组：

dp[i][j] = max(dp[i-1][j], dp[i][j-ai] + bi)，其中ai表示第i个物品的容量，bi表示第i个物品的价值。

解释一下这个状态转移方程：dp[i-1][j]表示不放第i个物品时的最大价值，dp[i][j-ai] + bi表示放第i个物品时的最大价值。我们要取这两个值中的较大值作为dp[i][j]的值。

最终，dp[N][M]即为所求。

注意：这个问题中的物品可以切割，因此每个物品可以选择放入任意数量，而不是只有放或不放两种选择。