题目描述 现在有一个背包(容器),它的体积(容量)为M,现在有N种物品(每个物品只有一个),每个物品的价值V[i]和占用空间W[i]都会由输入给出,现在问这个背包最多能携带总价值多少的物品? 设有N种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，从ｎ种物品中选取若干件，使其重量的和小于等于M，而价值的和为最大。N<=100,M<1000. 输入 第一行两个数：物品总数Ｎ，背包载重量M；两个数用空格分隔； 第二行N个数,为Ｎ种物品重量Wi(<1000)；两个数用空格分隔； 第三行N个数,为N种物品价值Vi(<1000); 两个数用空格分隔； 输出 一个整数，表示总价值。

这是一个经典的背包问题，可以使用动态规划求解。我们可以用一个二维数组 $dp[i][j]$ 表示在前 $i$ 种物品中选取若干件，使得它们的重量和不超过 $j$ 时的最大总价值。则有如下的状态转移方程：

$$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])$$

其中，$W[i]$ 和 $V[i]$ 分别表示第 $i$ 种物品的重量和价值。如果不选第 $i$ 种物品，则 $dp[i][j]$ 等于前 $i-1$ 种物品中选取若干件，使它们的重量和不超过 $j$ 时的最大总价值；如果选择第 $i$ 种物品，则 $dp[i][j]$ 等于前 $i-1$ 种物品中选取若干件，使它们的重量和不超过 $j-W[i]$ 时的最大总价值加上第 $i$ 种物品的价值。

根据状态转移方程，我们可以写出如下的 Python 代码实现：

def knapsack(N, M, W, V):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            if j >= W[i - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i - 1]] + V[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[N][M]

其中，$W$ 和 $V$ 分别是长度为 $N$ 的列表，表示 $N$ 种物品的重量和价值。最终返回的是 $dp[N][M]$，即在前 $N$ 种物品中选取若干件，使得它们的重量和不超过 $M$ 时的最大总价值。

时间复杂度为 $O(NM)$，空间复杂度为 $O(NM)$。如果要优化空间复杂度，可以使用滚动数组的方法，将二维数组压缩成一维数组，从而将空间复杂度优化为 $O(M)$。