01背包

背包中的物品的数量仅有一个，可以选择 装或不装

有N件物品和一个承重为begWeight的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，问：将哪些物品装入背包里物品价值总和最大。

暴力解法

看到这样的题目，也许从未接触过背包问题的就会直接尝试暴力解法—回溯
一个物品两个状态，装 或者不装，用回溯法搜索出所有的情况，时间复杂度：O(2n),n为物品的数量。
太拉垮了。

动态规划dp[i][j]

dp[i][j]

表示为 从0~i下标中的物品中任意取，放进剩余容量为j的背包中，价值总和最大的值。

状态转移公式

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
剩余容量为j 没拿i物品的情况， 剩余容量为j-weight[i] 准备拿i的情况

初始化

  • dp[i][0]一定为0；

    状态转移中有dp[i-1]则一定要初始化dp[0]的情况，然后递推从i=1开始。

  • dp[0][j]:从0~0中选东西=>也就是选不选0号的问题，剩余容量为j的背包能装的最大价值

=>当然就是能选0时就选

  1. // 初始化i为0时候的情况
  2. for (int j = bagWeight; j >= weight[0]; j--) {
  3.     dp[0][j] = dp[0][j - weight[0]] + value[0]; 
  4. }
  5. //好像其他初始化为0时，可以就这样简单地初始化 但是为了和前面的状态转移保持一致(?
  6. for (int j = bagWeight; j >= weight[0]; j--) {
  7.     dp[0][j] = value[0]; 
  8. }

为什么要倒序初始化呢？是因为正序的话，会重复地放入，而01背包问题中正是每个物品就只有一个。

  1. //正序 :(
  2. for (int j = weight[0]; j <= bagWeight; j++) {
  3.     dp[0][j] = dp[0][j - weight[0]] + value[0];
  4. }//自己模拟一下就知道了

除了保持一致的原因之外，使用倒叙初始化也是一种常用的方法来保证物品仅使用一次。

  • 其他dp[i][j]的初始化

如果所有重量均大于0，那么其他背包初始化为0就可以了。(好像是一句废话，重量还有≤0的？
实际上，背包问题只是一种模板，有时衍生出来的题目，他的权值是会小于0的。
有小于0的权值时就全部初始化为负无穷就好了。
vector<vector<int>> dp(weight.size()+1,vector<int>(bagweight+1,0))
如果是int，用_INT_MAX_表示正无穷，_INT_MIN_表示负无穷
如果是double，用_DBL_MAX_表示正无穷，_DBL_MIN_表示负无穷

遍历

  1. for(int i = 1; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
  3.         if (j < weight[i]) dp[i][j] = dp[i - 1][j]; //装不下时肯定不用考虑
  4.         else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  5.     }
  6. }

理论就到此为止了，当然 还有一种将二维数组压缩为一维数组的方法。

动态规划dp[j]

dp[j]

dp[j]表示剩余容量为j的背包能装的最大价值

状态转移公式

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

初始化

dp[0]=0,如所有物品均大于0，则其他物品也初始化为0就好，而若有负值，则需要初始化为负无穷。

遍历

  1. for(int i = 0; i < weight.size(); i++) { 
  2.     for(int j = bagWeight; j >= weight[i]; j--) { //当然要背包容量大于当前这个物品的价值
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }

注意这遍历背包容量时是倒序的，也是为了防止重复放入物品。
而二维时dp[i][j]来自dp[i-1][j]，dp[i][j]不会被覆盖。
并且一维遍历时必须是先遍历物品，再遍历背包大小。
—如果先遍历背包大小(已经说明了要倒序)，则每次都只会放入一个物品。

上点题目

力扣416.分割等和子集

我的题解
以下直接跳转题解

1049. 最后一块石头的重量 II

494. 目标和

474.一和零

L3-001 凑零钱 (30 分)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define FOR(i,n,m) for(int i =n;i<m;++i)
  6. int cost[10005], dp[10005][105]={0}, ans[10005], k = 0;
  7. bool _cmp(int a, int b){
  8.     return a > b;
  9. }
  10. //dp[i][j] 表示 1~i 枚硬币能否凑出面额为 j, 1代表可以，0代表不行。
  11. int main()
  12. {
  13.     ios::sync_with_stdio(false);
  14.     int n,//硬币数
  15.         m;//所需面额
  16.     cin>>n>>m;
  17.     for(int i = 1; i <= n; i++)
  18.         cin>>cost[i]; // 各个硬币面额
  19.     sort(cost + 1, cost + 1 + n, _cmp);//要求字典序小,那么就是先用小硬币
  21.     //初始化
  22.     for(int i = 0; i <= n; i++)
  23.         dp[i][0] = 1;
  25.     for(int i = 1; i <= n; i++){//遍历硬币
  26.         for(int j = 1; j <= m; j++){//遍历面额
  27.             if(j - cost[i] >= 0 && dp[i - 1][j - cost[i]] == 1)
  28.                 //不用这枚硬币时能凑出 j - cost[i]，用了自然能凑出 j
  29.                 dp[i][j] = 1;
  30.             else
  31.                 dp[i][j] = dp[i - 1][j];//否则就继承i-1的情况可能dp[i-1][j]就是1
  32.         }
  33.     }
  34.     if(dp[n][m] == 1){
  35.         while(m){
  36.             if(dp[n - 1][m - cost[n]] == 1){ 
  37.                 // //首先前提是dp[n][m]==1然后考虑前n-1块硬币时可以凑出m-cost[n]
  38.                 //那么dp[n][m]就是有前dp[n-1][m-cost[n]]凑出来的
  39.                 m -= cost[n]; ////找到了一块硬币了 那么我们就要找dp[n-1][m-cost[n]]的方案是啥了
  40.                 ans[k++] = cost[n];                ////记录一下 
  41.             }
  42.             n--;//不论第n块行不行那么肯定到前面
  43.         }
  44.         for(int i = 0; i < k - 1; i++) 
  45.             cout<<ans[i]<<" ";
  46.         cout<<ans[k-1]<<endl;
  47.     }else cout<<"No Solution\n";
  48.     return 0;
  49. }

完全背包

每个物品数量不限,可以选择 不选/选几个
基本上与01背包类似

遍历

01背包中,遍历背包容量时倒序遍历,是为了每个物品只添加一遍,而完全背包问题,物品有无限个,故正序遍历即可.

  1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }
  7. //内外层调过来也可以  当然 具体题目还要具体分析
  8. for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
  9.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  10.         if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  11.     }
  12.     cout << endl;
  13. }

上点题目

518. 零钱兑换 II 遍历顺序不能反的情况

这题是无序组合

[377. 组合总和 Ⅳ] 动态规划 完全背包 排序组合数

这题是排序组合

  • 这两题总结：
  • 如果求无序组合数就是外层物品，内层背包。
  • 如果求排列组合数就是外层背包，内层物品。

原因模拟一下就知道了
文字解释一下的话就是：先遍历背包再遍历物品时，每一个背包容量都计算了一轮价值。

[70. 爬楼梯] 动态规划版 温故而知新

[279. 完全平方数]动态规划 完全背包 求最小

[322. 零钱兑换] 动态规划 完全背包 最小值

[139. 单词拆分]动态规划 完全背包 有点难转化

多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

与01背包的关系—-每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了
力扣上没有找到题目，可能应用较少，那也就不要求掌握了。

树型背包

树形背包解决的问题是给你n个物品，但物品有依赖关系
a依赖b，b依赖c，选a就必须选b，选b就必须选c，
一个物品只能依赖一个物品，但一个物品可以被多个物品依赖，
这里就能看出来这是一个树。叫
你选择n物品可以使得价值最大，价值为多少？

直接从题目入手上手吧。

题目

P2014 [CTSC1997] 选课

先构建一个虚拟头——虚拟课程：没有先行课的先修课，则包含N个结点的森林就转换为了 N+1 个结点的树，其中结点0为根节点。（因为一开始可能是无根的，不好操作）
设 dp[x][t]为以x为根的子树中，选取 t 门课能获取的最高学分，设x的子节点集合为 Son(x),子节点个数为 p = |Son(x)|，选择x这门课后，对于x的每个子节点y，以y为根的子树中选修 t -1 门课程，并且在满足 t - 1 门课程基础上获得最多的学分。
初始
t=0时，显然dp[x][t] = 0
状态转移方程
t>0时，状态转移方程
背包问题 - 图1
其实也就是分组背包模型，有 p = |Son(x)|组物品，每组物品有 t-1 

  1.  #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. typedef pair<int, int> PII;
  5. #define FOR(i, n, m) for (int i = n; i < m; ++i)
  7. const int N = 310;
  8. //链式前向星存图
  9. struct node {
  10.   int v;        ///终端点
  11.   int next;     ///下一条同样起点的边号
  12.   int w;        ///权值
  13. } edge[N * 2];  ///无向边，2倍
  15. int head[N];  /// head[u]=i表示以u为起点的所有边中的第一条边是 i号边
  16. int tot;  ///总边数
  17. int minn;
  18. void add(int u, int v) {
  19.   edge[tot].v = v;
  20.   // edge[tot].w=w;
  21.   edge[tot].next = head[u];
  22.   head[u] = tot++;
  23. }
  24. int n, m;
  25. int dp[N][N], val[N];
  26. void dfs(int u, int fa) {
  27.   dp[u][1] = val[u];  ///选一个肯定选自己这个结点
  28.   for (int i = head[u]; i != -1; i = edge[i].next) {
  29.     int v = edge[i].v;
  30.     /// if(fa==v) continue;
  31.     /// ///如果下一个相邻节点就是父节点，则证明到底层了，开始递归父节点的兄弟节点
  32.     dfs(v, u);
  33.     ///分组背包
  34.     for (int j = m; j > 0; j--)  ///背包容量，倒叙，保证没有重复的物品
  35.       for (int k = 0; k < j; k++)  ///选择用户
  36.       {
  37.         dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
  38.       }
  39.   }
  40. }
  41. int main() {
  42.   while (~scanf("%d%d", &n, &m)) {
  43.     if (n == 0 && m == 0) break;
  44.     memset(head, -1, sizeof(head));
  45.     memset(dp, 0, sizeof(dp));
  46.     tot = 0;
  48.     for (int i = 1; i <= n; i++) {
  49.       int w, v;
  50.       scanf("%d%d", &v, &w);
  51.       add(v, i);
  52.       val[i] = w;  ///题目直接给出第i节课的值
  53.     }
  55.     m++;  ///我们可以0当作根节点，因为有的课可能没有先修课
  56.     val[0] = 0;  ///虚拟构造了结点0
  57.     dfs(0, -1);
  58.     printf("%d\n", dp[0][m]);
  59.   }
  61.   return 0;
  62. }

0.0

完。