问题描述： 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积恰好为背包容量V，且总价值最大。 输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N≤1000, 0<V≤50000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例： 8

这是一道经典的背包问题，可以使用动态规划来解决。

定义状态：dp[i][j] 表示考虑前 i 件物品，背包容量为 j 时，可以获得的最大价值。

状态转移方程：对于第 i 件物品，有两种情况，一种是不放进背包，此时最大价值为 dp[i-1][j]；另一种是放进背包，此时最大价值为 dp[i-1][j-vi]+wi。因此，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-vi]+wi)

初始状态：dp[0][j] = 0，dp[i][0] = 0。

最终答案：dp[N][V]。

Python 代码如下：

相关问题

题目描述 现在有一个背包(容器),它的体积(容量)为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)$。

问题 B: 01背包问题之2

题目描述

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。1<=N<=1000,1<=V<=1000,1<=vi,wi<=1000。

求将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。输出最大价值。

输入格式

第一行两个整数 $N$，$V$，用空格隔开，分别表示物品数量和背包容积。

接下来 $N$ 行，每行两个整数 $v_i$，$w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

样例输入

4 5
1 2
2 4
3 4
4 5

样例输出

8

算法1

(01背包) $O(NV)$

状态表示：设 $f[i][j]$ 表示前 $i$ 个物品，体积不超过 $j$ 的情况下的最大价值。

状态转移方程：$$ f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) $$

时间复杂度：$O(NV)$

C++ 代码

算法2

(01背包+滚动数组) $O(NV)$

状态表示：设 $f[i][j]$ 表示前 $i$ 个物品，体积不超过 $j$ 的情况下的最大价值。

状态转移方程：$$ f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) $$

时间复杂度：$O(NV)$

C++ 代码