目录

• 🌟一、了解动态规划DP
• 🌟二、闫式DP分析法
• 🌟三、01背包
• • • 一维写法 [优化：对代码等价变形]
    • 终极版本
• 🌟四、完全背包
• 🌟五、多重背包
• 🌟六、分组背包问题
• 🌟七、个人总结
• • 01背包 & 完全背包
  • 多重背包&多组背包
• 🌟 八、文章参考
• 🌟 九、最后

前言
欢迎关注我的专栏,准备写完算法基础所有题解🚀🚀🚀 专栏链接

🌟一、了解动态规划DP

何为DP？中文翻译为动态规划，很怪，个人认为还是叫做动态递推比较合适。

指的是将一个复杂的问题，分解成简单的问题（用一种递归的方式）——WIKI
本质：分治（与递归没有本质区别）+ 最优解 ，很多就是一些细节的不同。

🌟二、闫式DP分析法

y总的方法

🌟三、01背包

• [0-1]背包基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
  题目
  

闫式DP分析
①状态表示

• 集合f[i][j]:所有只从前i个物品中选,并且总体积≤j的选法的 【核心】请记住这句话，DP就是一直围绕这句话实现的
• 属性：MAX
  

②状态计算

• 当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1个物品最优解：f[i][j] = f[i - 1][j]。
• 如果可以选 ：f[i][j] = f[i - 1][j - v[i]] + w[i]。

③二维分析过程↓

代码
二维写法
时间复杂度 O(n*m)

#include using namespace std;const int N = 1010;int n, m;int v[N], w[N];//v:体积  w：价值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 = 1; j <= m; j ++) {  f[i][j] = f[i - 1][j];     if (j >= v[i]) {   f[i][j] =max (f[i][j],f[i - 1][j - v[i]] + w[i]);     } }    }    cout << f[n][m] << endl;    return 0;}

一维写法 [优化：对代码等价变形]

优化↓

for (int i = 1; i <= n; i ++) { //for (int j = 1; j <= m; j ++) { 更改顺序     for(int j = m; j >= 0; j --) {     if (j < v[i]) {//体积超出背包容量，不选  //f[i][j] = f[i - 1][j];  f[j] = f[j] //优化     }     else  {//决策要不要选  //f[i][j] =max (f[i - 1][j],f[i - 1][j - v[i]] + w[i]);  f[i][j] = max(f[j], f[j - 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]); }} 

终极版本

#include using namespace std;const int N = 1010;int n, m;int v[N], w[N];//v:体积  w：价值int f[N];//集合表示 一开始全为0int 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] << endl;    return 0;}

🌟四、完全背包

• 与 [0-1]背包的区别 ——每件物品可以选无限次

  题目
  

闫式DP分析

先从朴素(baoli)算法 时间复杂度接近 O(n³)

优化：错位相减的思路↓

• 图中橘色部分与f[i,j-v]相差w
• 得到：f[i][j]=max(f[i-1][j],f[i,j-v]+w ) 完全背包
• 对比 ：f[i][j]=max(f[i][j],f[i,j-v]+w ) 01背包
  
  最终代码

#include using namespace std;const int N = 1010;int n, m;int v[N], w[N];//v:体积  w：价值int f[N];//集合表示 一开始全为0int 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] << endl;    return 0;}

🌟五、多重背包

• 与完全背包有点相似 —— 每件物品最多有 s[i]种选择
  
  用前面错位相减的思路 这道题用不了
  
• 如果一件一件选的话，暴力时间复杂度：O(n³) 而且数据类型还是1000 + 一定会TLE
  所以， 考虑二进制优化—> 优化后时间复杂度 : O(nlogn)
• 步骤 ：拆分第i件物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k) , s[i]-2^k+1 + 1.(C)[下图的C]，且k是满足s[i] - 2^k+1 + 1>0 的最大整数,并且C < 2^k+1。

举个栗子，如果s[i]为13，就将这种物品分成系数分别为1,2,4,6(C)的四件物品。

代码

#include using namespace std;const int N = 25000;//2000 * log2 1000int n, m;int v[N], w[N];int f[N];int cnt = 0;//记录物品编号int main () {    cin >> n >> m;    for (int i = 1; i <= n; i ++) { int a, b, s;//体积：价值：个数 cin >> a >> b >> s; int k = 1; while (k <= s) {     cnt++;     v[cnt] = a * k;      w[cnt] = b * k;     s -= k;     k *= 2;//二进制优化 } if (s >0) {//补上最后的C     cnt++;     v[cnt] = a * s;     w[cnt] = b * s; }    }    n = cnt; //更新n    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] << endl;    return 0;  }

🌟六、分组背包问题

• 与前面的背包的区别 ——前面背包都是每件物品选几次，而分组背包问题是第i组物品选哪个？
  题目

思路

把分组背包问题 化解为 01背包问题

AC代码

#include using namespace std;const int N = 110;int n, m;int v[N][N], w[N][N],s[N];//s：每组物品个数int f[N];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 ++) {   // 枚举每一组物品 s for (int j = m; j >= 0; j --)//从大到小枚举每一组体积 同前面背包     for (int k = 0; k < s[i]; k ++) { //枚举所有选择   if (v[i][k] <= j) {      f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);  }     }    }    cout << f[m] << endl;    return 0;  }

🌟七、个人总结

01背包 & 完全背包

• 原式：
  [01]f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
  完全背包f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);

• 一维：f[j] = max(f[j], f[j - v[i]] + w[i])[相同]

for(int i = 1; i <= n; i++) { for(int j = m; j >= v[i]; j --) { //01背包     // for(int j = v[i]; j <= m; j --) { //完全背包   f[j] = max(f[j], f[j - v[i]] + w[i]); }    } 

• 为什么01背包 按照V…0 逆序，而完全背包于此相反？
  如果转移的时候用的是上一层i - 1的状态的话，就从大到小来枚举体积[可以保证我们算体积 所用到的体积都是没有被计算过的 ] 即要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来的。。如果是本层i的状态的话（完全背包），于此相反就要从小到大来枚举体积【因为完全背包：每种物品可选无限件，考虑选第i件物品的时候，却正需要一个可能已选入第i种物品的子结果f[i][j-v[i]]】。

多重背包&多组背包

• 多重背包：采用二进制优化为01背包问题
• 多组背包：多了枚举每一组物品，从而转化为01背包问题

🌟 八、文章参考

y总的算法基础课

🌟 九、最后

分享一段学习中看到的快乐

感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞鼓励下🌹🌹🌹