AcWing 2.01背包问题如何优化算法求解？

本文共计874个文字，预计阅读时间需要4分钟。

题目+有+N+件物品和一个容量是+V+的背包。每件物品只能使用一次。+第+i+件物品的体积是+v_i+，价值是+w_i+。求解将哪些物品装入背包，使得这些物品的总价值最大，且总体积不超过背包容量。

题目

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

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

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

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

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

数据范围 $0<N,V≤1000$ $0<v_i,w_i≤1000$ 输入样例

4 5 1 2 2 4 3 4 4 5

输出样例：

8

思路

状态表示：从前i个物品取且体积不超过j的价值的最大值 状态属性：最大值 状态计算：

对于第i个物品，存在两个选择，取或者不取 不取：f[i][j] = f[i- 1][j] 取：f[i][j] = f[i - 1][j - v] + w

通过以上思路两重循环遍历物品与体积，得到朴素算法。