一、题目
1、原题链接
2. 01背包问题 - AcWing题库
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
二、解题报告
思路来源：AcWing 2. 01背包问题（闫氏DP分析法） - AcWing
y总yyds
1、思路分析
二维dp
1）创建dp数组，dp[i][j]代表容量为j的背包可以放物品1~i中的任意物品背包所能达到的最大价值。
2）dp[i][j]的求取是两种情况中的最大值，第一种情况是dp[i-1][j]，代表不放第i件物品，下一次只从前i-1件物品中来选择物品放入；第二种情况是dp[i-1][j-v[i]]+w[i]，代表放第i件物品，所以背包中就必须得有i物品的位置，所以背包容量得减去i物品的体积，同时背包的价值也要加上i物品的价值，因为本次已经选了i物品，所以下一次就不能再选i物品，所以i-1。我们选择这两种情况中的最大值，作为dp[i][j]的最大值。
所以，递推方程为：dp[i][j]=max(dp[i-1][j],dp[i-1] [j-v[i]]+w[i])
3）针对背包容量为0或物品为0时（也就是数组第一列和第一行），dp的数组的值初始化均为0，其他值都可通过递推式求得（通过它左上方某个元素和它正上方的元素通过递推式求得）。
4）两层for循环遍历物品和背包容量，遍历顺序怎样都可以，因为我们无论怎样遍历都可以通过递推方程算出相应的值。对dp数组赋值，最后输出dp[N][V]，即为所求。
一维dp
1）在二维dp的情况下，我们可以优化一下空间，将二维数组压缩为一维数组，这个一维数组始终存储的是上一行的dp值，需要算本次的dp值，只要通过上一层的dp值也就是原数组值进行逐个更新即可。
2）思路与二维dp相同，所以递推方程也很类似：dp[j]=max(dp[j],dp[j-v[i]]+w[i])，仅仅是去掉了第一维的下标，将多个物品压缩在一行，每次更新某个元素，我们更新成了下一行该位置元素的值。
3）两层for循环分别遍历物品和背包，不可颠倒，而且背包容量需倒序遍历。因为我们将物品这一维给去掉了，所以第一次遍历数组中存放的是物品1在不同容量背包下所能达到的最大价值，我们需要遍历所有的物品在不同容量背包中所能带来的最大价值，而每次遍历物品都会依托于它的上一行，也就是它的上一个物品的所有dp值（对于二维dp来说就是上一行的值），如果先遍历背包的话，我们当前dp数组存储的不是上一行的dp值，而是一列值（就是在一定背包容量下，不同物品所带来的价值），这显然与我们预期不符。而遍历顺序由于在二维递推中，当前值取决于它左上方某个元素和它正上方的元素，而一维递推直接把它所在这一行和它上一行压缩在了同一行中，所以递推只取决于了它左边的元素，针对某一次更新dp数组，首先，我们可以知道现在未更新的dp数组存储的是上一个物品的所有情况的最大价值，我们需要在此基础上更新出我们该行的dp值，而且是根据左边元素进行更新，如果我们也从左边开始更新，先更新数组第一个元素，然后数组第一个元素的值已经更新成了新的值，接下来，第二个元素更新，这时候发现它的左边元素（也就是第一个元素）已经更新了，不是上一行的值了，而我们需要上一行的值来进行更新，所以就会发生错误，我们从右往左开始倒序遍历就不会出现这种情况（这就很类似数组的插入操作，我们插入了一个元素到数组中，我们需要从插入位置开始逐个更新数组值，我们也是从数组最后一个元素来操作，依次向后挪，如果从插入位置开始挪的话，后面的值就都被前面的元素值给覆盖掉了）。
4）对dp数组赋值，最后输出dp[V]，即为所求。
2、时间复杂度
时间复杂度均为O(n^2)
3、代码详解
二维dp
#include <iostream>
using namespace std;
int dp[1010][1010];
int v[1010];
int w[1010];
int main()
{ int N,V;
cin>>N>>V;
//注意下标，物品编号从1开始，下标为0的物品代表什么也不放
for(int i=1;i<=N;i++){
cin>>v[i]>>w[i];
}
//i从1开始，i从0开始会导致数字下标越界
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
//如果当前背包还能放下第i件物品才与不放i物品时背包的最大价值比较
if(j-v[i]>=0)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
//如果放不下物品i，就不放物品i
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[N][V];
return 0;
}
一维dp
#include <iostream>
using namespace std;
int dp[1010];
int v[1010];
int w[1010];
int main()
{ int N,V;
cin>>N>>V;
//注意下标，物品编号从1开始，下标为0的物品代表什么也不放
for(int i=1;i<=N;i++){
cin>>v[i]>>w[i];
}
//i从1开始，i从0开始会导致数字下标越界
for(int i=1;i<=N;i++){
for(int j=V;j>=0;j--){
//如果当前背包还能放下第i件物品才与不放i物品时背包的最大价值比较
if(j-v[i]>=0)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
//如果放不下物品i，就不放物品i
else
dp[j]=dp[j];
}
}
cout<<dp[V];
return 0;
}
在上面代码的基础上可以再简化一下代码，得到最终优化版代码如下：
#include <iostream>
using namespace std;
int dp[1010];
int v[1010];
int w[1010];
int main()
{ int N,V;
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--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[V];
return 0;
}
