/* 第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 ​ 值。

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

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

using namespace std;

const int N = 1010;

int f[N][N];
int w[N], p[N];
int n, m;

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

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (j >= w[i])
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + p[i]);
        }

    vector<int> res;
    int j = m;
    for (int i = n; i; i -- )
        if (f[i][j] != f[i - 1][j])
        {
            res.push_back(i);
            j -= w[i];
        }

    cout << f[n][m] << ' ' << j << endl;
    for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i] << ' ';

    return 0;
}

该代码使用二维数组 `f[i][j]` 表示考虑前 `i` 件物品，背包容量为 `j` 时的最大价值。初始化时 `f[0][j] = 0`，考虑第 `i` 件物品时，若不装入，则 `f[i][j] = f[i - 1][j]`，若装入，则 `f[i][j] = f[i - 1][j - w[i]] + p[i]`。最终输出的是最大价值和背包的剩余容量，以及每个物品被选中的数量。

现有n种物品，对1<=i<=n，第i种物品的重量为正整数w i ​ ，价值为正整数p i ​ ，背包能承受的最大载重量为正整数M，要求找出这n种物品的一个子集，使得子集中物品的总重量不超过M且总价值尽量大。0/1背包问题要求物品或者整件装入背包中，或者根本不装入(即不能装入物品的一部分)，所以x i ​ 限定只能取值0或1。 输入格式: 第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w i ​ ； 第3行是各物品的价值p i ​ ，背包容量和物品重量都为整数。 输出格式: 第1行是所选物品的价值之和，以及重量之和； 第2行是各物品装入背包的量，即x i ​ 值。

这是一个经典的0/1背包问题，可以用动态规划求解。

设 dp[i][j] 表示前 i 个物品，放入容量为 j 的背包中所能获得的最大价值。则状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + pi)

其中 wi 和 pi 分别表示第 i 个物品的重量和价值。

最后，回答你的问题，输入格式为：

第一行，两个正整数 M 和 n，表示背包容量和物品数量。

第二行，n 个正整数，表示每个物品的重量。

第三行，n 个正整数，表示每个物品的价值。

输出格式为：

第一行，一个正整数，表示所选物品的最大价值和总重量。

第二行，n 个 0 或 1，表示每个物品是否被选中。