现有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，表示每个物品是否被选中。

相关问题

使用C语言实现代码：现有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 ​ 值。 输入样例1: 6 3 2 3 4 1 2 5 输出样例1: 6 6 1 0 1

以下是使用动态规划实现 0/1 背包问题的 C 语言代码：

#include <stdio.h>
#define MAX_N 1000
#define MAX_M 1000

int w[MAX_N], p[MAX_N]; // 物品的重量和价值
int f[MAX_N][MAX_M]; // f(i,j) 表示前 i 件物品放入容量为 j 的背包中所得到的最大价值
int x[MAX_N]; // x(i) 表示第 i 件物品是否放入背包中，0 表示不放，1 表示放

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;
    scanf("%d%d", &m, &n);
    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) {
        for (int j = 0; j <= m; ++j) {
            if (j < w[i]) {
                f[i][j] = f[i - 1][j];
            } else {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + p[i]);
            }
        }
    }
    int ans_p = f[n][m], ans_w = 0;
    int j = m;
    for (int i = n; i >= 1; --i) {
        if (f[i][j] > f[i - 1][j]) {
            x[i] = 1;
            ans_w += w[i];
            j -= w[i];
        }
    }
    printf("%d %d\n", ans_p, ans_w);
    for (int i = 1; i <= n; ++i) {
        printf("%d ", x[i]);
    }
    printf("\n");
    return 0;
}

输入样例：

6 3
2 3 4
1 2 5

输出样例：

6 6
1 0 1

现有n种物品和一个可承载M 重量的背包，n种物品的重量分别为(w 1 ​ , w 2 ​ , …, w n ​ )，n种物品放入背包所获得的效益分别是(p 1 ​ , p 2 ​ , …, p n ​ ) (p i ​ >0)，p i ​ 和w i ​ 均是正整数，若将物品i的一部分x i ​ (0<=x i ​ <=1)放入背包，则所获得的效益是p i ​ x i ​ ，问采用怎样的装包方法会使装入背包物品的总效益为最大？第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w i ​ ； 第3行是各物品的价值p i ​ 。第1行是所选物品的最大价值之和； 第2行是各物品装入背包的量x i ​ 。要求保留小数点后两位，第三位按照四舍五入处理。用c语言实现

这是一个经典的背包问题，可以使用动态规划算法来解决。具体思路如下：

1. 定义状态：设dp[i][j]表示前i件物品放入容量为j的背包中所获得的最大价值。

2. 状态转移方程：对于第i件物品，有两种情况：放入背包和不放入背包。如果放入背包，则可以得到dp[i-1][j-w[i]]+p[i]的价值；如果不放入背包，则可以得到dp[i-1][j]的价值。因此，状态转移方程为：dp[i][j] = max(dp[i-1][j-w[i]]+p[i], dp[i-1][j])。

3. 初始化：当容量为0时，无论有多少件物品，背包中的价值都为0；当物品数量为0时，无论背包容量为多少，价值也都为0。

4. 求解：最终的结果为dp[n][M]，即前n件物品放入容量为M的背包中所获得的最大价值。

5. 装包方法：由于动态规划只求出了最大价值，需要再进行一次遍历，确定每种物品放入背包的数量。具体做法是从dp[n][M]开始，逆推回去，如果dp[i][j]等于dp[i-1][j]，说明第i件物品没有放入背包中；否则，第i件物品放入了背包中，其放入数量为x[i]=(M-w[i])/w[i]。

以下是C语言实现代码：

#include <stdio.h>
#include <math.h>

int main() {
    int M, n;
    scanf("%d%d", &M, &n);
    int w[n+1], p[n+1];
    double x[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 dp[n+1][M+1];  // 定义状态数组
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;  // 初始化
            } else if (j >= w[i]) {
                dp[i][j] = fmax(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);  // 状态转移方程
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    int max_val = dp[n][M];  // 最大价值
    printf("%d\n", max_val);

    for (int i = n; i >= 1; i--) {
        if (dp[i][M] > dp[i-1][M]) {
            x[i] = (double)(M-w[i]) / w[i];  // 计算放入数量
            M -= w[i] * x[i];
        } else {
            x[i] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        printf("%.2lf ", x[i]);
    }
    printf("\n");

    return 0;
}

示例输入：

10 5
2 3 4 5 9
3 4 5 8 10

示例输出：

29
0.00 0.00 1.00 0.00 1.00