动态规划——背包问题（详解）

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

动态规划是我最早接触的算法，一开始非常简单，固定模板题，后来愈发愈发难起来了，条件，状态压缩等等，难点主要是，状态怎么表示，状态转移方程怎么写，这篇文章将会从背包五大问题详解，希望能帮助到大家去类比，思考其他动态规划题目。

首先先来看看动态规划的定义：
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

看完定义我们开始应用了！来看基本的01背包问题，也是最经典的动态规划01背包问题（点此跳转题目，下同）
[ps:建议而外开个网页去打开题目链接，用Ctrl+tab食用更佳]

这题所求的是V容积下能够装的物品的最大值。很显然有容积的限制有时候你不能全部都装，又有体积和价值的不确定性，可能你选小体积的反而会有更大的价值，如果去暴力枚举时间复杂度呈指数显然不能ac，那么就需要六大算法之一动态规划了。

明确的一点此题是求最大值，而每个物品至多选一次，也就是只有选和不选俩个状态。我们可以一个一个物品去决策这个物品是该选还是不该选，这只需要一个max函数就能完成了。现在的问题是如何去定义，怎么去记录这个决策过程。依靠现有的知识能储存多组数据的只有数组了，我们可以先定义一个二维数组dp[N][N]去记录这个过程。

int dp[N][N]; //dp[i][j]表示容积为j的背包只装前i个物品可以达到的最大价值

这也是动态规划的第一步，明确数组的含义或者集合的含义。

接下来可以一个一个去决策了，先预知一下，肯定需要一个for循环去枚举物品，枚举完物品又需要一个for循环去枚举体积。在选或不选的情况下去择优，更新dp[i][j]，n2的时间复杂度，显然对付这题很容易了。

for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= m; j++) {
        dp[i][j] = dp[i-1][j]; //一开始是都选择不装
        if(j>=v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]);  
        //只有物品体积大于背包容积了才可以开始决策择优选或不选。
    }
}

那么最终答案就是dp[n][m],在只考虑前n个物品最大容积为m的背包可以装的物品的最大价值ac代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int dp[N][N];

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

    cout << dp[n][m] << endl;
    return 0;    
}

可能有人了解到可以空间压缩，滚动数组等等，在此先不讲，我们前面先讲思维。（有兴趣的我后面可能有浅讲一手，你们可以浅看一手）
好回归正题，我们来总结一下01背包问题。
首先是一个状态表示二维数组dp[][]，其次就是状态计算，怎么得到这个dp[i][j]，其实也挺简单，刚入门就是这么简单。

（建议消化一下，新知识的接纳需要沉淀）

好我们开始下一个 完全背包问题

与01背包不同 的 是，此问题的物品可以选择无限个;
状态表示跟01背包如出一辙，你问为什么，这么类似的题你不用类似的状态表示么，你还能想出其他的么，想出了当我没说

而状态计算跟刚刚也一样么，不错，一样的地方是一模一样的，只需要再添一重循环去循化个数就好了。这也是动态规划题目经常会遇到的设定，会给出体积限制，数量限制等等限制。代码如下
 

#include<iostream>

using namespace std;

const int N = 1010;

int dp[N][N];
int v[N],w[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++) cin>>v[i]>>w[i];

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

    cout<<dp[n][m]<<endl;
}

欸，复制过去为什么没ac，哈哈显然对于这道题n3的时间复杂度就tle了，这里先不说ac代码了，如果你仔细看完我对01背包的描述，这上面的代码应该是一边过，模拟一下代码就好了，很清晰。

接下来是 多重背包问题

与上述俩个问题不同的是既不是只能选一个也不是无限选，多重背包问题中是每个物品有数量限制，只能选几个。
这就是数量限制了，加嘛，加条件而已，谁都会。

#include <iostream>

using namespace std;

int dp[105][105];
int v[105],w[105],s[105];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&s[i]);
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=s[i];k++){
                if(j>=k*v[i]){
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
                }
            }
        }
    }
    
    printf("%d",dp[n][m]);
    return 0;
}

欸，为什么这题n3方的时间复杂度既然过了，因为这题数值范围比较小的说（不然你能过？？）

三题下来貌似很简单嘛，就很模板化了，接下来继续看 分组背包问题

此题与上述三题又有点不一样了。他将所有物品分成几个组，欸每组只能选几个。他不关心你每个能取几个了，他关心你每组能取几个了。emm稍有变通一下，我们刚刚关心每个第一重循环就去枚举物品个数，那我们现在关系每组，就只需要第一组去枚举组数就好了。

#include <iostream>
using namespace std;

const int N=110;
int dp[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];  //读入
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j];  //不选
            for(int k=0;k<s[i];k++){
                if(j>=v[i][k])  dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<dp[n][m]<<endl;
}

最后最后就是混合背包问题了，顾名思义，将上述背包混合起来，有的关心个数，有的关心组数，有的有条件限制，有的有数量限制，请听题 混合背包问题

如果你会了这题，那么证明你不是小白了，因为二维很难做，在此先不贴ac代码了。
好我们认识了这么多的背包问题，也算是动态规划入门了，现在你应该也对动态规划有所了解了，总比贪心好做吧！我们来归纳一下基础的动态规划题。

根据闫氏DP分析法，总的包括俩部分：
一部分是状态表示：也就是你需要去找一个集合去不重不漏的把所有情况涵盖在内，之后是解释这个集合的属性，可能是最大值，最小值，也可能是数量，直观感受就是去描述你这个数组代表着什么；
另一部分就是去状态计算：去写状态转移方程，直观的就是去想你当前这个单元是有哪几部分构成，如何去决策择优。例如01背包问题，dp[i][j]里面由dp[i-1][j]和dp[i-1][j-v[i]]+w[i]俩部分构成。咳咳肯定有小伙伴懵逼，我来翻译一下。就是说在容积为j的背包只挑前i个物品的最大价值可能是在容积为j的背包只挑前i-1个物品的最大价值，也可能是在容积为j-v[i]的背包只挑前i-1个物品的最大价值（第i个已经挑了）有没有顿悟了（没有在返回几行再看一遍/头槌）。至此动态规划–背包问题入门思维版已经结束了，相信你对背包问题已经了解了，慢慢感受状态表示和状态计算的魅力吧。