/* 第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）。否则，递归地考虑选择当前物品和不选择当前物品两种情况，取两者中价值更大的一种。同时，记录下选择与否的情况，以便输出解。

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

相关问题

动态规划解决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，表示每个物品是否被选中。