动态规划（DP）之闫式分析法

小明 2025-05-08 02:54:52 9

动���规划（DP）：是运筹学的一个分支，是求解决策过程最优化的过程

适用场景：用于求解具有某种最优性质的问题

闫式分析法基本思想：将待求解问题分解成若干个子问题，求解子问题的数学关系式，然后从这些子问题的关系式拼接成原问题的解法，然后将问题的条件从低到题目条件分层计算，需要注意的是经过分层得到的答案往往不是互相独立的，保存已解决的低层答案，在计算下一层或高层数据结果时再找出已求得的答案用以避免大量的重复计算，节省时间

优化方向：DP的所有优化都是对代码的等形变换，它和题目无关，和代码的逻辑有关

代码编写：使用DP应该是使用循环，将运算过程逐渐算出，即层次计算，先计算出底层的数据然后存储，在计算高层数据时再调用所需存储的计算结果，来达到避免重复计算

子问题分解关系式限制：

  1. 不重复
  2. 不遗漏

闫式分析法解题步骤：将DP问题中的重要信息提取出来，将题目化成状态表示、状态计算，而状态表示又分为集合和属性，以经典的01背包问题来举例，如下图：

在01背包问题中一共有2^n次方个方案，而求的是其价值最大的方案，在只考虑前i个物品时，分为考虑第 i 个物品和不考虑第 i 个物品，也就是将一个大问题分为了两个子问题。

将两个子问题求解：在求解考虑第i个物品时，需确定背包剩余容量是否能装下第 i 个物品

问题代码表示
考虑第 i 个物品f ( i-1，j )
不考虑第 i 个物品f ( i-1，j - v[ i ]) + w[ i ]
代码（暴力）：01背包问题（一般写法）
#include
#include
using namespace std;
//题目所定义的物品最大数
const int N = 1010;
//输入的物品数n、背包容量m
int n,m;
//存储物品的体积、价值
int v[N],w[N];
//二维数组解
int f[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i > v[i] >> w[i];
    }
    
    //循环的是物品数，表示的是考虑前i个物品
    for(int i = 1 ; i  m;
    for (int i = 1; i > v[i] >> w[i];
    for (int i = 1; i = v[i]; j -- ){
            //权值大于时，才更新
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout
The End

标签：

微信