题目链接：https://www.acwing.com/problem/content/description/2/
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入描述
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出描述
输出一个整数，表示最大价值。
0<N,V≤1000
0<vi,wi≤1000
示例
输入
4 5
1 2
2 4
3 4
4 5
输出
8
分析
约定
我们记第i件物品的体积和价值为v[i],w[i]
状态表示
f(i,j)表示满足如下条件的方案的最大价值：
- 仅从前i件物品中选择
- 所选取的物品体积小于等于j
状态划分
对于f(i,j),存在两种情况：
- 选了第i件物品
- 没选第i件物品
状态转移方程
对应状态划分，我们便可以得到相应的状态转移方程：
- f(i,j)=f(i-1,j)
- f(i,j)=f(i-1,j-v[i])+w[i]
显然，我们要取的f(i,j)应当是两者的最大值，因此最终的状态转移方程如下：
f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i])
总结
以上，是以f(i,j)这样一个二维的函数来求解本问题的思路，我们可以想象出一张二维的表格，行对应i，列对应j，求解的过程其实就是一行一行填表的过程，不断利用之前求出的结果，最终得到最终答案。
优化
对于这样一个填表的过程，由状态转移方程可以发现，要得到新的一行数据，只需要上一行的数据，我们没有必要将每一行数据都保存下来，因此我们就可以将二维的状态表示优化成一维的，在原有思路的指导下做出改变。改动时的易错点见代码注释。
二维解法AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
int n, V;
int v[N], w[N];
int f[N][N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= V; j++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) //此处加以判断防止数组下标越界
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][V] << endl;
return 0;
}
一维解法AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
int n, V;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
{
for (int j = V; j >= v[i]; j--)
{
//f[j]=f[j] 对应二维，应是我们思维的一步，理解后可去掉
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
//第二维的循环顺序改为由后向前，且终点改为了v[j]
/*顺序更改：得到新行需要上一行的数据(某一元素正上方的数据和左上方的数据)，因此如果继续从前向后，会覆盖上一行的数据，致使新行后面的数据无法计算*/
/*终点更改：防止越界*/
cout << f[V] << endl;
return 0;
}