首页 > 其他分享 >动态规划详解

动态规划详解

时间:2024-04-02 22:31:54浏览次数:21  
标签:状态 求解 int 问题 详解 动态 规划

动态规划详解

动态规划(Dynamic Programming,简称DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。在计算机科学中,动态规划是解决优化问题的一个强大工具。

一、动态规划的基本思想

动态规划的基本思想与分治法类似,也是将待求解的问题分解成若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

与分治法最大的差别是:适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

二、动态规划的基本要素

  1. 最优子结构性质:当问题的最优解包含了其子问题的最优解时,就称该问题具有最优子结构。动态规划算法正是利用了这种最优子结构性质,通过子问题的最优解来构造原问题的最优解。

  2. 无后效性:即某阶段状态一旦确定,则此后过程的演变不再受此前各种状态及决策的影响。也就是说,“未来与过去无关”,只与当前的状态有关。

  3. 子问题的重叠性:动态规划算法将原问题分解为若干子问题,然后逐个求解。这一点与分治法类似。区别在于,子问题之间不是独立的,一个子问题的解在下一阶段决策中可能会被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

三、C语言实现动态规划的基本步骤

  1. 划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

  2. 定义状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

  3. 确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

  4. 寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

以上就是用C语言实现动态规划的基本步骤。在实际编程中,我们还需要注意数据的存储和访问方式,以及算法的时间复杂度和空间复杂度等问题。

四、C语言动态规划示例——背包问题

背包问题是一类典型的动态规划问题。问题描述如下:有N件物品和一个容量为V的背包。第i件物品的重量是weight[i],得到的价值是value[i]。求解将哪些物品装入背包可使价值总和最大。

以下是一个用C语言实现的背包问题的动态规划解法:

#include <stdio.h>  
#include <stdlib.h>  
  
int max(int a, int b) {  
    return a > b ? a : b;  
}  
  
int knapsack(int W, int wt[], int val[], int n) {  
    int i, w;  
    int K[n + 1][W + 1];  
  
    // Build table K[][] in bottom up manner  
    for (i = 0; i <= n; i++) {  
        for (w = 0; w <= W; w++) {  
            if (i == 0 || w == 0)  
                K[i][w] = 0;  
            else if (wt[i - 1] <= w)  
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);  
            else  
                K[i][w] = K[i - 1][w];  
        }  
    }  
  
    return K[n][W];  
}  
  
int main() {  
    int val[] = {60, 100, 120};  // 价值数组  
    int wt[] = {10, 20, 30};     // 重量数组  
    int W = 50;                  // 背包容量  
    int n = sizeof(val) / sizeof(val[0]);  // 物品数量  
    printf("Maximum value that can be put in a knapsack of capacity %d is %d\n", W, knapsack(W, wt, val, n));  
    return 0;  
}


以上代码通过二维数组K[][]来保存子问题的解,其中K[i][w]表示前i个物品,当前背包容量为w时的最大价值。然后通过两层循环来遍历所有的子问题,并根据状态转移方程来更新K[][]数组的值。最后返回K[n][W]即可得到原问题的解。

标签:状态,求解,int,问题,详解,动态,规划
From: https://blog.csdn.net/qq_43341279/article/details/137108761

相关文章

  • 动态规划区间DP
    动态规划区间DP普通区间DP石子合并(蓝桥官网1233)#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=300;intn,a[N],s[N],f[N][N];signedmain(){cin>>n;memset(f,127,sizeof(f));//初始化f为较大值for(inti=1;i<=......
  • 可视化红黑树详解(gif图演示,洛谷P3369 普通平衡树)
    写在前面推荐一个很实用的工具:红黑树可视化本文参考OIwiki中的红黑树代码,读者也可以参考该篇解析(写得还是很不错的),不过OIWiki里删除后平衡维护的Case4和Case5在代码细节上稍微有些问题(把c......
  • 【嵌入式智能产品开发实战】(十四)—— 政安晨:通过ARM-Linux掌握基本技能【链接静态库与
    目录链接静态库动态链接与地址无关的代码全局偏移表延迟绑定共享库政安晨的个人主页:政安晨欢迎 ......
  • 动态sql实现修改
     在Mybatis内,根据某个条件进行修改,普通修改进行选择性修改时会对未修改的字段进行null了。使用动态sql,<if></if>进行判空实现。if与test属性联合使用。<updateid="updateDictById">updatexz_dict_type<set>......
  • vue3+ant-design-vue - 最新实现“侧边动态导航栏+面包屑导航“功能,vue3+ant后台管理
    效果图在vue3+antdesignvue后台管理系统中,详细完成菜单导航+面包屑动态联动功能效果,支持缓存功能、配置简洁、自动跟随route路由进行变化、自动匹配菜单和面包屑导航的文字等,超详细实用的示例demo全部源代码。提供详细示例源代码,新手小白直接复制稍微改下配置就能用了,快......
  • 自然语言处理基础知识入门(二) Word2vec模型,层次softmax,负采样算法详解
    文章目录前言一、Word2vec模型1.1什么是Word2vec模型?1.2Word2vec模型是如何训练?1.3Word2vec最简单版本整体过程1.4Word2vec详细过程1.5CBOW整体过程1.6Skip-gram整体过程二、优化算法2.1层次softmax2.1.1哈夫曼树2.1.2算法详细逻辑2.2负采样策略总结......
  • .NET Emit 入门教程:第六部分:IL 指令:3:详解 ILGenerator 指令方法:参数加载指令
    前言:在上一篇中,我们介绍了ILGenerator辅助方法。本篇,将详细介绍指令方法,并详细介绍指令的相关用法。在接下来的教程,关于IL指令部分,会将指令分为以下几个分类进行讲解:1、参数加载指令:ld开头的指令,单词为:loadargument2、参数存储指令:st开头的指令,单词为:store3、创建实......
  • HTTP请求消息数据格式详解(请求头,请求行,请求体)
    HTTP:概念:HyperTextTransferProtocol超文本传输协议传输协议:定义了,客户端和服务器端通信时,发送数据的格式特点:基于TCP/IP的高级协议默认端口号:80基于请求/响应模型的:一次请求对应一次响应无状态的:每次请求之间相互独立,不能交互数据历史版本:1.0:每一次请求响应都会建立新的......
  • Flutter应用发布流程详解:从开发到上架一站式指南
     引言Flutter是一款由Google推出的跨平台移动应用开发框架,其强大的性能和流畅的用户体验使其备受开发者青睐。然而,开发一款应用只是第一步,将其成功上架到苹果商店才是实现商业目标的关键一步。本文将详细介绍如何使用Flutter将应用程序上架到苹果商店,让您的应用更快地触达用户,......
  • Python加载C语言动态库
    ★背景说明1.python是一门胶水语言,可以通过加载动态库的方式在一个项目中运行不同语言的程序2.通过动态库加载其他语言的方式可以解决多线程GIL使用C解释器无法并发运行的问题★在Linux中运行C代码:编辑C语言代码//hello.c//c代码作为启动文件必须加include<stdio......