算法分析03--动态规划

这篇具有很好参考价值的文章主要介绍了算法分析03--动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

4.动态规划法

4.1 动态规划的基本思想

4.1.1 动态规划的基本思路

动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合用动态规划法求解的问题,经分解得到的子问题往往不是独立的。若用分治法来解这类问题, 则相同的子问题会被求解多次, 以至于最后解决原问题需要耗费指数级时间。然而,不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案, 在需要时再找出已求得的答案, 这样就可以避免大量的重复计算, 从而得到多项式时间的算法。为了达到这个目的, ** 可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到, 只要它被计算过, 就将其结果填入表中 **。这就是动态规划法的基本思路。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中, 可能会有许多可行解, 每个解都对应于一个值, 我们希望找到具有最优值(最大值或最小值)的那个解。

4.1.2 动态规划的步骤

设计一个动态规划算法, 通常按照以下几个步骤进行。
(1) 找出最优解的性质, 并刻画其结构特征。
(2) 递归地定义最优解的值。
(3) 以自底向上的方式计算出最优值。
(4) 根据计算最优值时得到的信息, 构造一个最优解。

4.1.3 何时使用动态规划?

那么何时可以应用动态规划来设计算法呢?对于一个给定的问题, 若其具有以下两个性质, 可以考虑用动态规划法来求解。
(1) 最优子结构。如果一个问题的最优解中包含了其子问题的最优解, 就说该问题具有最
优子结构。当一个问题具有最优子结构时, 提示我们动态规划法可能会适用, 但是此时贪心策略可能也是适用的。
(2) 重叠子问题。重叠子问题指用来解原问题的递归算法可反复地解同样的子问题, 而不
是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时, 就说该问题包含重叠子问题。此时若用分治法递归求解, 则每次遇到子问题都会视为新问题, 会极大地降低算法的效率, 而动态规划法总是充分利用重叠子问题, 对每个子问题仅计算一次, 把解保存在一个在需要时就可以查看的表中, 而每次查表的时间为常数。

4.2 动态规划的典型实例

4.2.1 0-1背包问题

有n个物品, 第1个物品价值为Vi,重量为wi, 其中vi和wi均为非负数, 背包的容量为W,
W为非负数。现需要考虑如何选择装入背包的物品, 使装入背包的物品总价值最大。
满足约束条件的任一集合(x1, …,xn) 是问题的一个可行解,问题的目标是要求问题的一个最优解。

例题1,背包容量为10,物品重量分别为2,3,4,5;价值为3,4,5,6,求背包中能装下物品的最大价值。

物品分别编号为1,2,3,4,列表如下:

物品/容量 1 2 3 4 5 6 7 8 9 10
1 0 3 3 3 3 3 3 3 3 3
2 0 3 4 4 7 7 7 7 7 7
3 0 3 4 5 7 8 9 9 12 12
4 0 3 4 5 7 8 9 10 12 13

由表可知,表中每一个元素的值取决于它正上方的值和它左上角的值,
如果当前背包容量小于物品重量,那么当前物品不放入背包;如果当前背包容量大于物品重量,那么当前物品可以放入背包,也可以不放入背包,取它左上角和放入物品后价值的最大值。

java代码如下:


public class knapsack01 {
    public static void main(String[] args) {
        int[] weight = {2,3,4,5};
        int[] value = {3,4,5,6};
        int w = 10;
        knapsack(weight,value,w);
    }

    public static void knapsack(int[] weight,int[] value,int w){
        int n = weight.length;
        int[][] dp = new int[n+1][w+1];
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=w;j++){
                //如果当前背包容量小于物品重量,那么当前物品不放入背包
                if(j<weight[i-1]){
                    dp[i][j] = dp[i-1][j];
                //如果当前背包容量大于物品重量,那么当前物品可以放入背包,也可以不放入背包,取两者最大值  
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);
                }
            }
        }
        System.out.println("最大价值为:"+dp[n][w]);
        //回溯找出选择的物品
        int k = n;
        int l = w;
        while(k>0&&l>0){
            if(dp[k][l] == dp[k-1][l]){
                k--;
            }else {
                System.out.println("选择了第"+k+"个物品,重量为:"+weight[k-1]+",价值为:"+value[k-1]);
                l = l - weight[k-1];
                k--;
            }
        }
    }
}

上述代码的时间复杂度为O(nw),n为物品个数,w为背包容量

4.2.2 最长公共子序列LCS

如果用穷举法求解该问题, 列举出X的所有子序列, 一一检查其是否是Y的子序列, 并随时记录所发现的公共子序列, 最终求出最长公共子序列, 时间复杂度为0(2mn), 是指数级的时间复杂度, 对千长序列来说不可行。而动态规划法可以有效地求解最长公共子序列问题。

求解思路:假设有字符串x,其索引范围为0-i,字符串y,其索引范围为0-j,那么最长子序列长度为dp[i][j],如果两个字符串最末尾的元素x[i]=y[j]相等,则dp[i][j]=dp[i-1][j-1]+1,如果两个字符串最末尾的元素x[i]=y[j]不相等,则有两种情况。情况1,dp[i][j]=dp[i-1][j],情况2,dp[i][j]=dp[i][j-1],这两种情况需要取其最大者,因此dp[i][j]=max{dp[i-1][j],dp[i][j-1]}。文章来源地址https://www.toymoban.com/news/detail-493566.html

public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String x = " ABCBDAB";
        String y = "BDCABA";
        lcs(x,y);
    }
    public static void lcs(String x,String y){
        int xlen = x.length();
        int ylen = y.length();
        int[][] maxSub = new int[xlen+1][ylen+1];
        //初始化数组第一列
        for(int i=0;i<=xlen;i++){
            maxSub[i][0] = 0;
        }
        //初始化数组第一行
        for(int j=0;j<=ylen;j++){
            maxSub[0][j] = 0;
        }
        for(int i=1;i<=xlen;i++){
            for(int j=1;j<=ylen;j++){
                //若末尾元素相等,则最长公共子序列长度加1
                if(x.charAt(i-1)==y.charAt(j-1)){
                    maxSub[i][j] = maxSub[i-1][j-1]+1;
                //若末尾元素不相等,则最长公共子序列长度为两个子序列中较长的那个
                }else {
                    maxSub[i][j] = Math.max(maxSub[i-1][j],maxSub[i][j-1]);
                }
            }
        }
        System.out.println(maxSub[xlen][ylen]);
        int j = xlen;
        int k = ylen;
        StringBuilder sb = new StringBuilder();
        //从后往前遍历,找出最长公共子序列
        while(j>0 && k>0){
            if(x.charAt(j-1)==y.charAt(k-1)){
                sb.append(x.charAt(j-1));
                j--;
                k--;
            }else {
                if(maxSub[j-1][k]>maxSub[j][k-1]){
                    j--;
                }else {
                    k--;
                }
            }
        }
        //因为从后往前遍历,所以需要反转字符串
        System.out.println(sb.reverse().toString());
    }
}

到了这里,关于算法分析03--动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 6-1 求解资源分配问题(动态规划法)[PTA]

    6-1 求解资源分配问题(动态规划法) 某公司有3个商店A、B、C,拟将新招聘的5名员工分配给这3个商店,各商店得到新员工后,每年的赢利情况如下表所示,求分配给各商店各多少员工才能使公司的赢利最大。 函数接口定义: 裁判测试程序样例: 输入格式: 第一行输入商店数

    2024年02月12日
    浏览(68)
  • C++每日一练:打家劫室(详解动态规划法)

    这题目出得很有意思哈,打劫也是很有技术含量滴!不会点算法打劫这么粗暴的工作都干不好。 提示:以下是本篇文章正文内容,下面案例可供参考 题目名称: 打家劫舍 题目描述: 一个小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素

    2024年02月02日
    浏览(46)
  • 最优控制理论 九、Bellman动态规划法用于最优控制

    尽管DP也是最优控制理论的三大基石之一,但长久以来,动态规划法(Dynamic Programming)被认为只能在较少控制变量的多阶段决策问题中使用,维数灾难使他不可能搜索得了整个连续最优控制问题的高维状态空间,因此仍然只能在一些维数较低的离散决策变量最优选择中取得较好

    2024年02月01日
    浏览(45)
  • 回溯法,分支限界法,动态规划法求解0-1背包问题(c++)

    问题描述 给定n种物品和一背包。物品i的重量是wi0,其价值为vi0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 搜索空间: 子集树(完全二叉树) 约束函数(进包用): 如果当前背包中的物品总重量是cw,前面k-1件物品都已经决定是否进包,那

    2024年02月10日
    浏览(57)
  • 算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    题目链接🔥🔥 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于

    2024年02月10日
    浏览(39)
  • 算法分析与设计--动态规划

    一、动态规划简介 二、动态规划求解步骤 三、动态规划典型应用 数字三角形问题 最大子段和问题 0-1背包问题 四、最长公共子序列问题 动态规划求解 五、总结 算法语言--java语言 动态规划算法通常用于求解具有某种最优性质的问题。动态规划与分治算法类似,其基本思想也

    2024年02月07日
    浏览(69)
  • 算法设计与分析—动态规划例题

    题目描述 求FIB数列第n项的值 输入 输入一个整数n,表示需要输出FIB数列第n项的值 输出 输出FIB数列第n项的值 样例输入  复制 样例输出  复制 提示 题目描述 长江游艇俱乐部在长江上设置了n (n=10)个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的

    2024年04月13日
    浏览(41)
  • 【算法分析与设计】动态规划(下)

      若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的 子序列 是指 存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij 。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。   给定2个序列X和Y,当另

    2024年02月08日
    浏览(50)
  • 【算法分析与设计】动态规划(上)

       理解动态规划算法的概念 。    掌握动态规划算法的基本要素 :   (1) 最优子结构性质   (2) 重叠子问题性质   掌握设计动 态规划算法的步骤 :   (1) 找出最优解的性质,并刻划其结构特征 。   (2) 递归地定义最优值 。   (3) 以自底向上的方式计算

    2024年02月08日
    浏览(44)
  • 算法分析与设计---分治+动态规划

    1.分治法 适用条件: 问题规模缩小到一定程度容易求解 问题可以分解为若干个规模较小的 相同 子问题,即问题具有最优子结构( 使用分治法前提 ) 可以利用子问题的解合并为该问题的解( 决定是否使用分治法 ) 各个子问题 相互独立 ,即子问题之间不包含公共子问题(

    2024年02月07日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包