动态规划（资源优化版）

特点

  • 有限的资源组合出尽可能大的答案，答案关于资源数单调不减，这里的单调不减指的是资源越多答案只可能越优，不可能变差

线性 dp（基础版）

特点

  • 只在一个维度资源有限，另外的维度视作无限资源

解决方法

  • 资源从小到大递推
  • 求出转移方程

例题

1、牛吃草问题

问题描述

有 n 块草地坐标范围 Li-Ri，每块草地有 Ri-Li+1 份草，不能选择有重叠区域的草地，最多能吃多少草？

代码逻辑
  • 有限的资源（n 块草地）吃到尽可能多的草，草地变多，答案单调不减
  • 只要有草就能吃，容量无限
  • 吃草的终点坐标从小到大递推，那么资源也就从小到大递推
  • dp[i]>dp[j]当且仅当 dp[i]中选择了右端点处于 j+1 到 i 的草地
  • 状态转移时，尽可能从近的状态转移（因为答案关于资源单调不减）
  • 选 i 为终点的草地，转移方程见 for 循环, 不选 i 为终点的草地，转移方程 dp[i]=dp[i-1]，两者选择一个答案最优的
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> right_left[maxn];
//对于每一个右端点，存下它的所有左端点,right的下标表示右端点，对应的容器中的值表示与此右端点对应的左端点
   for(int i=1;i<=right_max;i++) //right_max为数据中最大的右端点
   {
    	   dp[i] = dp[i-1]; //不选以i为终点的草地

          for(int ver : right_left[i])
          {
              if(dp[ver-1] + i - ver + 1 > dp[i] )
                  dp[i] = dp[ver-1] + i - ver + 1;
   //如果dp[i]从下标ver到i-1的dp值转移而来，这个dp值要么等于dp[ver-1]，要么这个dp值对应的状态和当下冲突
          }
   }
cout<<dp[right_max];

2、物品摆放问题

问题描述

有 n 个位置可以摆放物品，物品无限，但要求两者之间至少有 k 个空位，什么物品都不摆放也算一种方案，一共有多少种摆放方案？

代码逻辑
  • 有限的资源（n 个位置）求尽可能多的摆放方案，位置变多，答案单调不减
  • 只要有合法位置就能摆物品，物品无限
  • 摆放物品的终点从小到大递推，那么资源也就从小到大递推
  • 第 n 个位置要么摆放物品要么不摆放物品，两种对应的情况数相加得到答案
核心代码
1
2
3
4
5
6
7
8
9
dp[0] = 1; //只考虑0个位置，即什么都不放
for(int i=1;i<=n;i++)
   {
       dp[i] = dp[i-1]; //第i个位置不摆放物品
       //加上第i个位置摆放物品的方案
       dp[i] += i-k+1>0 ? dp[i-k+1] : 1;
  //i-k+1<=0时，只有前面什么物品都不放才能在i这里放物品，只加一种情况
  //i-k+1>0时，从i-k+2到i-1必然都没有物品且第i位有物品，后面定了，所以前面有多少种方案就加多少种方案
   }

滚动数组

特点

  • 有限的资源和有限的容量组合出尽可能大的结果，相同的资源条件下，结果随容量单调不减，但各结果无递归关系，当下结果只与前一个资源条件下的结果有关

例题

1、奇怪的数列

问题描述

n 个数字构成和为 s 的数列，其中 ai只能加 a 或者减 b 到 ai+1，求满足条件的数列有多少个

代码逻辑
  • 把+a 和-b 都视作+P
  • 求和时，a0-an-1的+P 的权重为 0 到 n-1，$$\sum_{i=0}^{n-1}$$ai = na0+$$\frac{n(n-1)P}{2}$$，$$\frac{n(n-1)}{2}$$里面有 i 次是+a 时，权重分配方案为 dpi,各种分配方案求出来的 a0是定值，如果是整数，那么答案加 dpi，否则，答案加 0
  • 有限的资源（n 个数列元素），有限的容量（分配给+a 的权重至多为$$\frac{n(n-1)}{2}$$,这里 n 表示当下资源规模）外循环表示资源从小到大
  • dpij=dp(i-1)j+dp(i-1)(j-i)，把第一层维度放到外循环上
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dp[0]=1; //规模为1时，无权重可分，只有dp[0]为1，其他为0
for(int i=1;i<n;i++) //问题规模为1+i，终点为下标为i的数列元素
   {
       //滚动数组先默认继承了上一个状态的值，相当于i号元素权重不给+a的方案数
       //然后再加上i号元素的权重赋给+a的方案数
       for(int j=(i+1)*i/2;j>=i;j--)
           dp[j] += dp[j-i]; //如果j本身小于i，那么i号元素权重赋给+a的方案数为0，也就是dp[j]+=0
   }
for(int i=0;i<=n*(n-1)/2;i++)
   {
       int a0 = s + b * ( n*(n-1)/2 - i ) - a * i ;
       if (a0%n==0)
           ans += dp[i];
   }

2、背包问题（基础版）

问题描述

有一个容量 V 的背包，有 n 个物品体积分别为 vi，求出背包用掉的最大容量

代码逻辑
  • 有限资源（n 个物品），有限容量（V）要求组合出尽可能大的体积
  • dpij=dp(i-1)j+dp(i-1)(j-v)+v 可以把第一维度体现在外循环上
  • 状态转移时，用尽可能贴近的 dp 值做转移，因为答案单调不减
核心代码
1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)  //考虑前i件物品
   {
       //默认第i件物品不放入
       for(int j=V;j>=V-v[i];j--)
       {
           //如果第i件物品可以放入，且放入结果更大，就放入
           if( dp[j] < dp[ j - v[i] ] + v[i] )
               dp[j] = dp[ j - v[i] ] + v[i];
       }
   }

3、多重背包

问题描述

背包有 V 容量，n 种商品分别有价值量 wi，体积 vi和数量 si，求出背包可以装下的最大价值

代码逻辑
  • 有限的资源（n 种商品），有限的容量（背包容量 V）求出尽可能大的价值量
  • dpij=dp(i-1)j+dp(i-1)(j-v)+w 可以把第一维度体现在外循环上
  • 外循环表示物品种类一件件增加，问题规模从小到大
  • 每考虑一种商品需要考虑 si次状态转移，把 si二进制分解，减少计算次数
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int i=1;i<=n;i++)
   {
       cin>>w>>v>>s;
       for(int j=1;j<=s;s-=j,j+=j) // 每次循环代表的物品体积j*v，价值j*w
       {
           //默认这件物品不放入
           for(int k=V;k>=j*v;k--)
           {
               //如果这件物品可以放入，且放入结果更大，就放入
               if(dp[k] < dp[k-j*v] + j * w)
                   dp[k] = dp[k-j*v] + j * w;
           }
       }
       if(s>0)  //s未被分尽
       {
    		for(int k=V;k>=s*v;k--)
           {
               if(dp[k] < dp[k-s*v] + s * w)
                   dp[k] = dp[k-s*v] + s * w;
           }
       }
   }

背包问题拓展

例题

1、完全背包

问题描述

背包容量 V，n 种商品具有价值量 wi和体积 vi，每种商品都可以无限次购买，求背包装下的最大价值

代码逻辑
  • 有限的资源（n 种商品），有限的容量（背包容量 V），组成尽可能大的价值
  • dpij=dp(i-1)j(j<vi)，dpij=max(dpij , dpi(j-vi)+wi) 先用外循环继承上一个状态的结果，再用内循环从前向后递推
核心代码
1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
   {
       for(int j=v[i];j<=V;j++)
       {
        	dp[j] = max(dp[j],dp[ j - v[i] ] + w[i])
       }
   }

二维 dp

特点

状态转移时，必须考虑两个维度

例题

1、砝码称重

题目描述

N 个砝码分别重 Wi，求出最多可以称量多少种重量

代码逻辑
  • 如果只用一维数组，那么 dpi能表示的信息只有前 i 个砝码可以称出多少种重量，但是考虑状态转移的时候发现，由于不知道到底具体哪些重量可以被称出来，所以无法排重。比如 dpi=3 时，如果四个砝码可以称出重量 10，无法确定 dp4应该比 dp3大还是和 dp3一样大
  • 用二维数组 dpij表示前 i 个砝码是否可以称出重量 j
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=1;i<=n;i++) //资源从小到大遍历
  {
      for(int j=sumW;j>=1;j--)
      {
         	if(dp[i-1][j]) //继承
              dp[i][j] = true;
         	else if(j==w[i]) //只用i这个砝码
              dp[i][j] = true;
          else if(dp][i-1][ j + w[i] ]) //第i个砝码和物品在天平同一边
              dp[i][j] = true;
          //第i个砝码与物品分别在天平的两边
         	else if(j<w[i] && dp[i-1][ w[i] - j ])
              dp[i][j] = true;
          else if(j>w[i] && dp[i-1][ j - w[i] ])
              dp[i][j] = true;
      }
  }

状态压缩 dp

特点

总状态数不多，可以用二进制表示

例题

1、买糖果

问题描述

商店有 n 包糖，每包糖里面有 k 种口味，一共有 m（<=20）种口味，每包糖里面的口味用数字 1 到 20 表示，最少买几包糖可以吃遍所有口味

代码逻辑
  • 用二进制对口味编码，口味的数字为 i，那么二进制第 i-1 位就为 1，编码出来的一个二进制数就代表一种口味组合
  • 资源从小遍历到大，如果某种口味组合可以被买到，那么它再加上当下的这包糖果的组合也可以被买到
核心代码_预处理
1
2
3
4
5
6
7
8
9
10
11
12
//求出每包糖果的口味组合
for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=k;j++)
       {
           cin>>taste;
           pac[i] |= ( 1<< (taste-1) );
       }
   }
max_taste = ( 1<<m ) - 1; //从第0位到第m-1位都是1
memset(dp,inf,sizeof(dp)); //初始化所有口味组合都无法买到
dp[0] = 0;  //口味组合：什么口味都不要，这种情况买0包就可以了
核心代码_状态转移
1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;i++)
   {
    	for(int j=0;j<=max_taste;j++)
       {
           if(dp[j]<inf) //可以买到口味组合j
           {
           //买到了口味组合j的基础上，买下当下这包糖果，可以让口味组合j|pac[i]所需的糖果更少，那么就更新答案
               dp[ j | pac[i] ] = min( dp[ j | pac[i] ], dp[j] + 1 );
           }
       }
   }