动态规划

从集合角度思考DP问题

动态规划的两个组成部分：

1. 状态表示F[i][j]：

   1. 这个状态表示了从起点（1，1）走到当前位置（i，j) 的全部路线的集合【隐式】
   2. 其值表示某种属性：最大值/最小值/数量

2. 状态计算：为了求解当前状态F[i][j]，即从起点（1，1）走到当前位置（i，j) 的全部路线的集合，可以采用分治法将集合给划分，划分一般依据“最后一步”来进行划分，即从上一状态走到当前状态的几种方式，从而分开计算上一状态后加上走到最后一步的值，最后根据所求属性进行选择判断。【划分满足不重不漏】

可以看出求的就是一张二维表，其时间复杂度就是O(n*m)

背包问题

练习题：背包问题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

01背包

01背包问题就是给一个容量为V的背包和N个物品，这N个物品有两种属性：价值V_i，重量W_i 。当每件物品最多只能选择一次，并且重量之和不能超过背包的容量时求能拿到的最大价值之和为多少？

问题分析

这种类型的题使用动态规划来解（算法就是要用问题映射问题来想解决方案），首先就要得到状态表示F[i][j]，其中 i 表示选择前 i 个物品 ，j 表示背包容量，F[i][j]就表示只从前 i 个物品中选择总体积小于等于 j 的所有选法，其属性值就是所有选法中的最大值。接下来就是状态计算，可以将F[i][j]划分为不选第i个物品（即从前i-1个物品中选择总体积小于等于 j 的所有选法）和选第i个物品（即选了第i个物品，并且总体积小于等于j的所有选法），第一个集合可以表示为F[i-1][j]，第二个集合可以表示为F[i-1][j-v_i] （第二个集合可以等效为选择前i-1个物品并总体积小于等于j-v_i加上选择了第i个物品的所有选法）。最后我们要求的就是F[N][V];

例题

采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

3

提示

【数据范围】

• 对于 $30\%$ 的数据，$M \le 10$；
• 对于全部的数据，$M \le 100$。

【题目来源】

NOIP 2005 普及组第三题

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int M=110,T=1010;
int t,m;
int v[M],w[M];
int f[M][T]={0};

int main(){
    cin >> t >> m;
    for(int i=1;i<=m;++i)cin >> w[i] >> v[i];
    for(int i=1;i<=m;++i){
        for(int j=0;j<=T;++j){
            f[i][j]=f[i-1][j];      //第一个划分的集合
            if(j>=w[i])f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);    //存在第二种划分的前提下是当前背包容量大于等于第i个物品的容量
        }
    }
    cout << f[m][t] << endl;
    return 0;
}

---

完全背包

有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品可以取无限次放入背包中，背包所有物品权重和最大是多少？

问题分析

这种题可以采用动态规划和贪心法进行解决，这里探讨动态规划法；同样需要解决两个问题，一个是状态表示F[i][j]，与01背包表示相同；另一个是状态计算，参考01背包问题，可以将F[i][j]表示的集合拆解为选0~k个第i个物品（k就是重量极限下的第i个物品个数），递推方程就是$F[i][j]=F[i-1][j-k*v[i]]+k*w[i]$，这样就需要三重循环进行计算，很容易造成超时，所以对方程进行分析：

$F[i][j]=max(F[i-1][j],F[i-1][j-v[i]]+w[i],F[i-1][j-2*v[i]]+2*w[i],...)——1$

$F[i][j-v[i]]=max(F[i-1][j-v[i]],F[i-1][j-2*v[i]]+w[i],...)——2$

从方程1中可以看出，第2项后面正好等于F[i][j-v[i]]+w[i]，因此递推方程可以优化为$F[i][j]=max(F[i-1][j],F[i][j-v[i]]+w[i])$

例题

疯狂的采药

与采药那一题的差别就是每种药的数量不限。原题链接

//二维的有些数据会超时，需要使用滚动数组解决
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const ll M=1e4+10,T=1e7+10;

ll m,t;
int a[M],b[M];

int main(){
    cin >> t >> m;
    vector<vector<ll>> f(m+1,vector<ll>(t+1));    //这样可以避免数组太大
    for(int i=1;i<=m;++i)cin >> a[i] >> b[i];
    for(int i=1;i<=m;++i){
        for(int j=0;j<=t;++j){
            f[i][j]=f[i-1][j];
            if(j>=a[i])f[i][j]=max(f[i][j],f[i][j-a[i]]+b[i]);
        }
    }
    cout << f[m][t] << endl;
    return 0;
}

---

多重背包

有n件物品，每件物品的重量为v[i]，价值为w[i]。现有一个容量为V的背包，问如何选择物品放入背包，使得背包内的物品的总价值最大。其中每件物品有s[i]件。

问题分析

因为每件物品的个数不同，因此可以将每件物品分为s[i]类物品，使得成为01背包问题【完全背包因为是无穷个，所以不采用此方式】，这样就与01背包问题完全相同了。但显而易见，若s[i]的个数太大，会导致物品数量急剧上升，从而超时，因此需要一种优化算法。这里采用二进制优化。

二进制优化

若一类物品的数量为1023件，若拆分成1023类物品，则每类物品的数量都为1，价值相同。朴素算法就是对这1023类物品做01背包【归根结底就是选择这类物品0~1023件】。

类别	价值	数量
1	x	1
2	x	1
...	x	1
1023	x	1

但若拆分成10类物品，每类物品的数量依次是1,2,4,8,...,512，价值相同。

类别	数量	价值
1	1	x
2	2	x
...	2^k	x
10	2^9	x

若对这10类物品做01背包，可以发现，对选择总和数量为0~1023件中任意一个数量，都可以得到。这样就等效了对1023类物品做01背包。这是为什么呢？

十进制数	二进制数
1	0000000001
2	0000000010
4	0000000100
8	0000001000
16	0000010000
32	0000100000
64	0001000000
128	0010000000
256	0100000000
512	1000000000

从二进制上看，就很显而易见了，这10个数就可以组成1~1023中任意一个数。这就是二进制优化。

推广为任意的数量s，则s就可以分为1，2，....，2^k，C【其中C<2^k+1,C=余数】。如s=1000，就可以分为1,2,4,8,...,256,489（1000-2⁹+1）。时间复杂度为

因此对于多重背包问题，就是将每件物品拆分成二进制优化数量的物品，然后对这些物品做01背包即可。价值数组和重量数组需要开到n*lgs（有n类物品，每类最大为s件，即最多总件数）或者所有件数之和

例题

宝物筛选

原题链接

题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为一个整数 $n$ 和 $W$，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

样例 #1

样例输入 #1

4 20
3 9 3
5 9 1
9 4 2
8 1 3

样例输出 #1

47

提示

对于 $30\%$ 的数据，$n\leq \sum m_i\leq 10^4$，$0\le W\leq 10^3$。

对于 $100\%$ 的数据，$n\leq \sum m_i \leq 10^5$，$0\le W\leq 4\times 10^4$，$1\leq n\le 100$。

#得用滚动数组才不会超时
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int N=1e5+10;
int n,W;
int v[N],w[N],s[N];

int main(){
    cin >> n >> W;
    int cnt=1;

    for(int i=1;i<=n;++i){
        int a,b,s;
        cin >> a >> b >> s;
        int k=1;
        while(k<=s){
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
            cnt++;
        }
        if(s>0){
            v[cnt]=s*a;
            w[cnt]=s*b;
            cnt++;
        }
    }
    n=cnt;
    vector<vector<int>> f(n+1,vector<int>(W+1));
    for(int i=1;i<=n;++i){
        for(int j=0;j<=W;++j){
            f[i][j]=f[i-1][j];
            if(j>=w[i])f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
        }
    }
    cout << f[n][W] << endl;
    return 0;
}

---

分组背包

有 n 件物品和一个大小为 m 的背包，第 i 个物品的价值为 w，体积为 v。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。

问题分析

同样考虑两个方面，状态表示F[i][j]，其表示为从前i个物品中选择出总容量不大于j的选法集合，其属性值表示这些集合中价值最大的选法的价值；另一个方面就是状态计算，就是分解集合，可以将F[i][j]表示的集合拆分成从这个组中选择0个，第1个...第k个物品；选择0个物品即$F[i][j]=F[i-1][j]$，选择第k个物品即$F[i][j]=max(F[i-1][j],F[i-1][j-v[i][k]]+w[i][k])$。

例题

通天之分组背包

原题链接

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1

45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

10

提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N=1010,M=1010;
int n,m;
vector<int> w[N],v[N];
int s[N]={0};
int f[N][M];

int main(){
    cin >> m >> n;
    for(int i=1;i<=n;++i){
        int a,b,c;
        cin >> a >> b >> c;
        w[c].push_back(a);
        v[c].push_back(b);
        s[c]++;
    }
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            f[i][j]=f[i-1][j];
            for(int k=0;k<s[i];++k){
                if(j>=w[i][k])f[i][j]=max(f[i][j],f[i-1][j-w[i][k]]+v[i][k]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

---

 

动态规划法求组合数

组合数即类似于 $C_n^m$，使用动态规划法的根据就是 $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$，即先从n个球中取出一个球，那么这个球就有两种情况，一种为满足条件，一种为不满足条件。则总的就是原组合数。根据动态规划，先初始化 C[i][0]=0，然后填表。

int main(){
    ll C[N][N];     //组合数数组
    for(int i=0;i<=n;++i){
        for(int j=0;j<=i;++j){
            if(j==0) C[i][j]=1;
            else C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
    return 0;
}