C语言设有背包问题的实例n=7,M=15,(w0,w1,...,w6)=(2,3,5,7,1,4,1),物品装入背包的收益为:(p0,p1,...,p6)=(10,5,15,7,6,18,13). 编程求其最优解和最大收益

我们可以使用动态规划来解决背包问题。具体步骤如下：

1. 定义一个二维数组dp，其中dp[i][j]表示前i个物品装入容量为j的背包中所能获得的最大收益。

2. 初始化dp数组，当背包容量为0时，无论有多少物品可选，收益都为0；当只有一件物品可选时，如果它的重量小于等于背包容量，则收益为该物品的价值，否则收益为0。

3. 遍历背包容量和可选物品，对于任意一个物品i和容量j，分两种情况考虑：

- 物品i不放入背包，此时最大收益为dp[i-1][j]；

- 物品i放入背包，此时最大收益为dp[i-1][j-w[i]] + p[i]，其中w[i]表示物品i的重量，p[i]表示物品i的价值。

取这两种情况的最大值作为dp[i][j]的值。

4. 最终dp[n][M]即为最优解，dp[n][M]的值即为最大收益。

根据上述算法，我们可以得到如下的C语言代码实现：

#include <stdio.h>
#define n 7
#define M 15

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

int main() {
    int w[n+1] = {0, 2, 3, 5, 7, 1, 4, 1};
    int p[n+1] = {0, 10, 5, 15, 7, 6, 18, 13};
    int dp[n+1][M+1] = {0};
    int i, j;

    // 初始化dp数组
    for (i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (j = 0; j <= M; j++) {
        dp[0][j] = 0;
    }
    if (w[1] <= M) {
        dp[1][w[1]] = p[1];
    }

    // 动态规划
    for (i = 2; i <= n; i++) {
        for (j = 1; j <= M; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i]);
            }
        }
    }

    // 输出结果
    printf("最优解为：");
    j = M;
    for (i = n; i >= 1; i--) {
        if (dp[i][j] > dp[i-1][j]) {
            printf("%d ", i);
            j -= w[i];
        }
    }
    printf("\n最大收益为：%d\n", dp[n][M]);

    return 0;
}

输出结果为：

最优解为：1 3 6 7 
最大收益为：38