第一行输入背包的最大承重量 M 和物品的个数 n (1<M<500，1<n<20)，第二行输入1至n个物品的重量，第三行输入1至n个物品的价值。输出最大可能的价值。

好的，我可以为您提供示例代码，使用动态规划算法解决这个问题。

M, n = map(int, input().split())  # 输入背包最大承重和物品个数
w = [0] + list(map(int, input().split()))  # 物品重量，加上一个0便于后面的代码实现
v = [0] + list(map(int, input().split()))  # 物品价值，同样加上一个0

dp = [[0] * (M+1) for _ in range(n+1)]  # 初始化dp数组

for i in range(1, n+1):
    for j in range(1, M+1):
        if j >= w[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][M])  # 输出最大可能的价值

上述代码中，我们使用了一个二维数组dp来记录每一种状态下的最大可能价值。其中，dp[i][j]表示在前i个物品中选择若干个放入容量为j的背包中所能获得的最大价值。

接下来，我们使用两重循环来枚举所有的状态，根据上述的状态转移方程来更新dp数组。最终，dp[n][M]就是背包中物品的最大价值。

希望这个示例代码可以帮助您解决问题！

相关问题

0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 【输入形式】 第一行输入物品的个数n和背包容量C。 第二行输入每个物品的价值v[i]. 第三行输入每个物品的重量w[i] 【输出形式】 第一行输出最大价值。

这是一个经典的动态规划问题，可以用01背包问题的动态规划思想来解决。

首先，我们定义一个二维数组dp，其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。

状态转移方程如下：

如果第i个物品的重量大于当前背包容量j，则不放入背包中，此时的最大价值为dp[i-1][j]。

如果第i个物品的重量小于等于当前背包容量j，则有两种选择：

1.不放入第i个物品，此时最大价值为dp[i-1][j]；

2.放入第i个物品，此时最大价值为dp[i-1][j-w[i]]+v[i]。

综上所述，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) (j >= w[i])

dp[i][j] = dp[i-1][j] (j < w[i])

最终的最大价值就是dp[n][C]，其中n为物品个数，C为背包容量。

以下是Python代码实现：

用C语言编写给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？ 在选择装入背包的物品时，对每种物品i只能有两种选择，装入或者不装入，不能装入多次，也不能部分装入。第一行输入物品的个数n。 第二行输入物品的重量序列w。(中间有空格） 第三行输入物品的价值序列v。（中间有空格） 第四行输入背包容量c。第一行输出装入背包的物品。（用0和1表示，中间无空格） 第二行输出最大价值。

这是一个经典的 0/1 背包问题，可以使用动态规划算法来解决。以下是 C 语言代码实现：

#include <stdio.h>
#define MAX_N 100
#define MAX_C 10000

int n, c;
int w[MAX_N+1], v[MAX_N+1];
int dp[MAX_N+1][MAX_C+1];

void knapsack() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            if (w[i] <= j) {
                dp[i][j] = dp[i-1][j-w[i]] + v[i];
                if (dp[i-1][j] > dp[i][j]) {
                    dp[i][j] = dp[i-1][j];
                }
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
}

void print_items() {
    int j = c;
    for (int i = n; i >= 1; i--) {
        if (dp[i][j] > dp[i-1][j]) {
            printf("1 ");
            j -= w[i];
        } else {
            printf("0 ");
        }
    }
    printf("\n");
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    scanf("%d", &c);

    knapsack();

    print_items();
    printf("%d\n", dp[n][c]);

    return 0;
}

输入示例：

5
2 2 6 5 4
6 3 5 4 6
10

输出示例：

0 0 1 0 1
15