经典动态规划——背包DP题目总结：0-1背包，对二维dp的初次接触

先来看模版题目：

1.小明的背包1

这个便是最经典的求最大价值的01背包问题：

暴力求解的话便是dfs每个选或不选，决策树的问题，这个时间复杂度太高了暂且不说。

设dp[i][j]为前i个物品装进容量为j的背包所能产生的最大价值；

接下来考虑状态转移方程：假设某种放的方法成功达到了最大值，对于这个方法：对于第i个物品来说，有两种可能的情况，第一种是这种方法包括他，第二种是不包括，取两种方法的最大值，

如果放入第i个物品的话，那么获得第i个物品的价值，接下来的背包就是从前i-1个元素中选择若干物品放入容量为v-w[i]的背包中，如果不放入，那么便是从i-1个物品中放入容量为v的背包中，

即

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);

边界处理问题：

这里边界的处理是由转移方程得到的，其实第二个for循环可以不用，赋值10086也是能通过的

dp[0][0]=0;
for(int i=1;i<=v;i++){
dp[0][i]=0;
}
for(int i=1;i<=n;i++){
dp[i][0]=0;
}

接下来来看状态转移的代码实现

for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
if(j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);

}

}

这里要考虑j<w[i]时是一定不能选的

这道题目还可以进行空间优化，因为这里状态转移方程只取决于上一维度的dp数组，这里j要从大到小遍历，否则每次更新将会覆盖上一层的元素，而这些元素可能在j更大时需要用到

for(int i=0;i<=v;i++){
dp[i]=0;
}

for(int i=1;i<=n;i++){
for(int j=v;j>=0;j–){
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}

}

01背包的进阶问题：完全背包：

这里物品不再是以1个了而是可以无限去选择了 1.小明的背包2 – 蓝桥云课

对于完全背包来说，dp数组的状态定义是不变的，但是状态转移方程要变了，这里如果选择拿的话就要枚举所有能拿的情况，一个？或者两个？或者更多，

for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
dp[i][j]=0;
for(int k=0;k<=j/w[i];k++){
dp[i][j]=max(dp[i][j],k*c[i]+dp[i-1][j-k*w[i]]);

}
}

完全背包的空间优化，时间优化：

先看时间优化：

对于第i个商品拿或者不拿，也可以看成不拿以及至少拿一个，既然是至少拿一个的话那可以先放一个进背包，就变成了dp[i][j-w[i]]+c[i]

for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++){
if(j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]);

}
}

同时空间也可以优化（注意这里就要从小到大遍历了）dp[j-w[i]]+c[i]这个是同一行的结果而非要上一行的结果。

for(int i=0;i<=v;i++){
dp[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}

背包dp的变种问题：

1，不再求最大价值，转而去求有多少种方案数的问题

U663298 疯狂的背包问题(3) – 01背包问题（计数组合问题） – 洛谷

这里dp数组的状态定义就要由最大价值改为方案数了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans=0;
int dp[1001][1001];
//dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]];
int w[1001];
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i];
}
dp[0][0]=1;
for(int i=1;i<=m;i++){
dp[0][i]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j>=w[i])
dp[i][j]=(dp[i-1][j]+dp[i-1][j-w[i]])%1000000007;
else
dp[i][j]=dp[i-1][j]%1000000007;
}
}
cout<<dp[n][m]%1000000007;

return 0;
}

2,无限背包变种：518. 零钱兑换 II – 力扣（LeetCode）

作者最近几天用脑过度了，待更新。。。

到这里，背包 dp 的核心内容就梳理得差不多了。我们从最经典的 01 背包出发，理解了状态定义、状态转移方程和边界处理，也掌握了空间优化的思路；接着扩展到完全背包，看到了枚举拿取数量的朴素写法，以及时间、空间上的双重优化；最后还介绍了背包 dp 的常见变种，比如求方案数的问题。背包 dp 是动态规划里非常基础也非常重要的一类模型，很多看似复杂的问题，最终都能化归到背包的框架下求解。希望这篇总结能帮你把背包 dp 的脉络理清楚，也欢迎在评论区交流你的想法，后续我会继续补充更多变种和实战题目。