目录

一、题目

1、原题链接

2、题目描述

二、解题报告

1、思路分析

2、时间复杂度

3、代码详解

一、题目

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 51 22 43 44 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 elsedp[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 elsedp[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;}