课前温习
初识DP
dp问题的优化：在基本形式dp上作等价变形。
dp问题的解题方法：
1）状态表示
集合
属性：最大值/最小值/数量。
2）状态计算
集合划分（不重不漏）
一、 背包问题
1、0-1背包问题
题目链接： 2. 01背包问题 - AcWing题库
1.1题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且 总价值最大 。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
0
输入样例：
4 5 1 2 2 4 3 4 4 5
输出样例：
8
1.2思路分析
1）状态表示
集合：所有选法。而且选法需要满足①只从前i件物品中选；②满足总体积<=j。
属性：f[i][j]表示满足条件集合中的最大价值。
2）状态计算
集合划分：分成两类①满足集合条件而且不选i；②满足集合条件而且选i。
计算：①f[i-1][j]；②先将所有集合中去掉第i件物品，然后求所有集合中的最大价值即f[i-1][j-v[i]]，最后再把第i个物品加上，得到最大价值f[i-1][j-v[i]]+w[i]。两者取最大即可求得f[i][j]的最大值，即 f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])。
1.3代码实现
#include <iostream> using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[N][N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; } //i=0，0=<j<=m时：放入0件物品时最大价值都是0，不需要初始化 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ //第一种情况一定存在 f[i][j]=f[i-1][j]; //第二种情况当j>=v[i]，即背包可以放下第i件物品时情况才存在 if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); } } cout<<f[n][m]; return 0; }
代码优化 ：计算数组f[i]这一层时，只用到了f[i-1]这一层，所以可以利用滚动数组（原理：两行的二维数组，交替使用来计算下面层的元素值）来实现。所以，f[j]=max(f[j],f[j-v[i]]+w[i])。
注意 ：背包容量需要从大到小遍历，即背包容量需逆序遍历，因为计算下一层时，如果从小到大遍历，则排在前面的就会先被更新成下一层的值，然后就把当前值给覆盖了，影响到了排在它后面的元素的更新。
优化代码
#include <iostream> using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[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=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; return 0; }
2、完全背包问题
题目链接： 3. 完全背包问题 - AcWing题库
2.1题目描述
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且 总价值最大 。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
0
输入样例：
4 5 1 2 2 4 3 4 4 5
输出样例：
10
2.2思路分析
1）状态表示
集合：所有选法。而且选法需要满足①只从前i件物品中选；②满足总体积<=j。
属性：f[i][j]表示满足条件集合中的最大价值。
2）状态计算
集合划分：按照第i个物品选几个来划分。
计算：①i个物品选0个：f[i-1][j]；②i个物品选1~k个：先将所有集合中去掉k个第i件物品，然后求所有集合中的最大价值即f[i-1][j-k*v[i]]，最后再把k个第i件物品加上，得到最大价值f[i-1][j-k*v[i]]+k*w[i]。将两种条件综合可得，f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])。
2.3代码实现
#include <iostream> using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[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++){ //物品i的个数不能超过背包只放物品i最多可以存放的个数 for(int k=0;k*v[i]<=j;k++){ f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); } } } cout<<f[n][m]; return 0; }
代码优化 ：
将原有递推式展开，f[i][j]除f[i-1][j]这一项，其余每一项都比f[i][j-v[i]]多w[i]，所以，f[i][j]除f[i-1][j]之外的最大值也比f[i][j-v[i]]的最大值多w[i]。所以 f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])。
优化代码
#include <iostream> using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[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++){ //第一种情况一定存在 f[i][j]=f[i-1][j]; //第二种情况当j>=v[i]，即背包可以放下第i件物品时情况才存在 if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]); } } cout<<f[n][m]; return 0; }
再次优化 ：与0-1背包问题转一维类似，但是背包容量要正序遍历，原因：要求f[i][j]需知道该层的f[i][j- v[i]]，因为f[i][j-v[i]]在f[i][j]之前，所以需要先更新f[i][j-v[i]]，然后再更新f[i][j]，也就是说需要从前往后遍历背包容量。
#include <iostream> using namespace std; const int N=1010; int n,m; int v[N],w[N]; int f[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=v[i];j<=m;j++){ f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; return 0; }
3、多重背包问题 1
题目链接： 4. 多重背包问题 I - AcWing题库
3.1题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且 价值总和最大 。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0
0
输入样例：
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
3.2思路分析
注：本题数据数据范围较小，可以完全利用完全背包的朴素思路来过掉。
1）状态表示
集合：所有选法。而且选法需要满足①只从前i件物品中选；②满足总体积<=j。
属性：f[i][j]表示满足条件集合中的最大价值。
2）状态计算
集合划分：按照第i个物品选几个来划分。
计算：①i个物品选0个：f[i-1][j]；②i个物品选1~k(k最大为s[i])个：先将所有集合中去掉k个第i件物品，然后求所有集合中的最大价值即f[i-1][j-k*v[i]]，最后再把k个第i件物品加上，得到最大价值f[i-1][j-k*v[i]]+k*w[i]。将两种条件综合可得，f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])。
3.3代码实现
朴素二维
#include <iostream> using namespace std; const int N=110; int n,m; int v[N],w[N],s[N]; int f[N][N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]>>s[i]; } for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ //和完全背包的条件类似：物品i的个数不能超过背包只放物品i最多可以存放的个数而且不能超过物品i的最大个数 for(int k=0;k<=s[i]&&k*v[i]<=j;k++){ f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); } } } cout<<f[n][m]; return 0; }
优化一维
#include <iostream> using namespace std; const int N=110; int n,m; int v[N],w[N],s[N]; int f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]>>s[i]; } for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ //和完全背包的条件类似：物品i的个数不能超过背包只放物品i最多可以存放的个数而且不能超过物品i的最大个数 for(int k=0;k<=s[i]&&k*v[i]<=j;k++){ f[j]=max(f[j],f[j-k*v[i]]+k*w[i]); } } } cout<<f[m]; return 0; }
4、多重背包问题 2
题目链接： 5. 多重背包问题 II - AcWing题库
4.1题目描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且 价值总和最大 。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0
0
0
提示：
本题考查多重背包的二进制优化方法。
输入样例：
4 5 1 2 3 2 4 1 3 4 3 4 5 2
4.2思路分析
无法依据完全背包优化方式进行优化 ，原因：因为完全背包问题中，每个物品的数量是无限的，即
f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2v[i]]+2w[i],…,f[i - 1][j - k * v[i]] + k * w[i],...);
f[i][j - v[i]] = max( f[i-1][j-v[i]] ,f[i-1][j-2v[i]]+w[i],…,f[i - 1][j - k * v[i]] + (k - 1) * w[i],...);
因为是无限项，所以第一个式子f[i][j]除去第一项f[i-1][j]后和第二个式子项数是完全相等的，而每一项仅仅相差一个w[i]，所以f[i][j-v[i]]+w[i]的最大值和f[i][j]去掉第一项后之后所有项的最大值相等，也就是说 f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])。
然而多重背包所放的每件物品都是有最大数量限制的，所以如上图，f[i][j]除去第一项后剩下的项数与f[i][j-v[i]]的项数不同，多了一个f[i][j-v[i]]的最后一项，所以不能像完全背包一样，像上面那样的优化。
优化方式（二进制优化）：将第i个物品分组打包，针对 每组可以选也可以不选 ，即 0-1背包问题 ，针对某一个s[i]
每次打包个数分别为：20，21，22，…，2k，而最后的 C<2(k+1)。
从1到2k可以凑出0 ~ 2~~(k+1)~~-1个第i个物品，在此基础上加上C之后可以拼出C ~ 2(k+1)-1+C个第i个物品，即[c~s]
由于C<2(k+1)，所以两个区间的并集就是 [0,S]。
所以可以总结出，我们可以将s[i]分组为 logS[i]个，可以将时间复杂度从O(NVS)降到O(NVlogS[i])。
4.3代码实现
#include <iostream> using namespace std; const int N=25000,M=2000; int n,m; int v[N],w[N]; int f[N]; int main() { cin>>n>>m; int cnt=0; //打包的组号 for(int i=1;i<=n;i++){ int a,b,s;//当前物品的体积、价值、个数 cin>>a>>b>>s; int k=1; //打包过程 //k<=s时可以分组打包 while(k<=s){ cnt++; v[cnt]=a*k; w[cnt]=b*k; s-=k; //每次分完一次后，物品总数减去k k*=2; //每次分组，物品个数为2的幂 } //如果没有正好分完，将剩余物品打包成一组。 if(s>0){ cnt++; v[cnt]=a*s; w[cnt]=b*s; } } n=cnt; //分组数即为物品数，每组有不同个物品，可选可不选，转化成0-1背包 //0-1背包 for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]; return 0; }
5、分组背包问题
题目链接： 9. 分组背包问题 - AcWing题库
5.1题目描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且 总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0
0
0
输入样例：
3 5 2 1 2 2 4 1 3 4 1 4 5
输出样例：
8
5.2思路分析
1）状态表示
集合：所有选法。而且选法需要满足①只从前i件物品中选；②满足总体积<=j。
属性：f[i][j]表示满足条件集合中的最大价值。
2）状态计算
集合划分：按照第i组物品选几个来划分。
计算：①第i组物品选0个：f[i-1][j]；②第i组物品选第k个：f[i-1][j-v[i][k]]+w[i][k]。将两种条件综合可得，f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k]]+w[i][k])。
注 ：遍历顺序：如果递推需要由上一层推得，则需要逆序遍历背包容量；如果递推需要由本层推得，则需要正序遍历背包容量。
可以类似优化为一维：f[j]=max(f[j],f[j-v[i][k]]+w[i][k])。
5.3代码实现
#include <iostream> using namespace std; const int N=110; int n,m; int v[N][N],w[N][N],s[N]; int f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++){ cin>>s[i]; for(int j=1;j<=s[i];j++){ cin>>v[i][j]>>w[i][j]; } } for(int i=1;i<=n;i++){ //背包容量逆序遍历 for(int j=m;j>=0;j--){ for(int k=1;k<=s[i];k++){ // f[j-v[i][k]]存在才判断是否更新最大，若不存在，f[j]=f[j] if(v[i][k]<=j){ f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } } cout<<f[m]; return 0; }
