首页 > 编程语言 >【算法】【动态规划】钢条切割

【算法】【动态规划】钢条切割

时间:2024-02-14 13:11:07浏览次数:30  
标签:map 钢条 递归 int 问题 算法 动态 切割

1  题目

来自算法导论的一道经典题目:

2  解答

动态规划原理
虽然已经用动态规划方法解决了上面问题,但是大家可能还跟我一样并不知道什么时候要用到动态规划。总结一下上面的斐波拉契数列和钢条切割问题,发现两个问题都涉及到了重叠子问题,和最优子结构。

①最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构,如果一个问题的解结构包含其子问题的最优解,就称此问题具有最优子结构性质。因此,某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时,用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

②重叠子问题

在斐波拉契数列和钢条切割结构图中,可以看到大量的重叠子问题,比如说在求fib(6)的时候,fib(2)被调用了5次,在求cut(4)的时候cut(0)被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题,不停的调用函数,而不是生成新的子问题。如果递归算法反复求解相同的子问题,就称为具有重叠子问题(overlapping subproblems)性质。在动态规划算法中使用数组来保存子问题的解,这样子问题多次求解的时候可以直接查表不用调用函数递归。

其实按我的理解:

(1)大问题能不能拆成小问题(没法拆成小问题,那还用什么动态规划。。。),小问题的解能不能推导出大问题的解(如果小问题推到不出大问题的解,那拆的还有什么意义呢?是不是)

(2)重复小问题(递归比如斐波那契,里边就有很多重复的递归操作比如 5 要求3和4,4 里边又要递归3 和2,计算3 重复了吧,很多的重复小问题,可以用备忘录也就是数组或者map缓存中间结果,或者自底向上的计算哈)

那么这个问题的解:我们用递归和动态规划来解一下:

2.1  递归

/**
 * 计算长度为 n 的钢条的最大收益
 * @param map 长度收益映射表
 * @param n 钢条长度
 * @return 最大收益值
 */
public static int maxIncome(int[] map, int n) {
    // 钢筋长度边界考虑
    int res = 0;
    if (n <= 0) {
        return res;
    }
    // 递归的话
    // n 的最大收益值 = 切割 n 次的最大收益(当 n = n 时,就是不切割的情况)
    for (int i = 1; i <= n; i++) {
        res = Math.max(res, map[i-1] + maxIncome(map, n - i));
    }
    return res;
}
public static void main(String[] args) {
    int[] map = new int[]{1, 5 ,8, 9, 10, 17, 17, 20, 24, 30};
    System.out.println(maxIncome(map, 4));
}

2.2  备忘录递归

/**
 * 计算长度为 n 的钢条的最大收益
 * @param map 长度收益映射表
 * @param n 钢条长度
 * @return 最大收益值
 */
public static int maxIncome(int[] map, int[] cache, int n) {
    // 钢筋长度边界考虑
    int res = 0;
    if (n <= 0) {
        return res;
    }
    // 先从缓存中拿,因为钢筋收益肯定是大于0的,所以这里大于0就表示有计算过
    if (cache[n] > 0) {
        System.out.println("命中缓存:" + n);
        return cache[n];
    }
    // 递归的话
    // n 的最大收益值 = 切割 n 次的最大收益(当 n = n 时,就是不切割的情况)
    for (int i = 1; i <= n; i++) {
        res = Math.max(res, map[i-1] + maxIncome(map, cache, n - i));
    }
    cache[n] = res;
    return res;
}
public static void main(String[] args) {
    // 长度收益
    int[] map = new int[]{1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    // 钢筋长度
    int n = 4;
    // 缓存
    int[] cache = new int[n + 1];
    System.out.println(maxIncome(map, cache, n));
    System.out.println(Arrays.toString(cache));
}

4里边会计算2,3里边也会计算2,所以2命中过一次

2.3  动态规划-自底向上

/**
 * 计算长度为 n 的钢条的最大收益
 * @param map 长度收益映射表
 * @param n 钢条长度
 * @return 最大收益值
 */
public static int maxIncome(int[] map, int n) {
    // 缓存
    int[] cache = new int[n + 1];
    // 自底向上 直接从1开始计算到n
    for (int i = 1; i <= n; i++) {
        int segRes = 0;
        for (int j = 1; j <= i; j++) {
            segRes = Math.max(segRes, map[j - 1] + cache[i - j]);
        }
        cache[i] = segRes;
    }
    return cache[n];
}
public static void main(String[] args) {
    // 长度收益
    int[] map = new int[]{1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    // 钢筋长度
    int n = 4;
    System.out.println(maxIncome(map, n));
}

3  小结

好久没看动态规划了= =,适应中....也感谢铁子的讲解:https://blog.csdn.net/u013309870/article/details/75193592 讲的挺好。

标签:map,钢条,递归,int,问题,算法,动态,切割
From: https://www.cnblogs.com/kukuxjx/p/18015118

相关文章

  • 预处理共轭梯度算法(Preconditioned Conjugate Gradients Method)
    预处理共轭梯度算法(PreconditionedConjugateGradientsMethod)给出百度百科上的解释:预处理共轭梯度法预处理共轭梯度法是。不必预先估计参数等特点。共轭梯度法近年来在求解大型稀疏方程组中取得了较好的成效。理论上普通的共扼梯度法对于对称超正定方程,只要迭代步数达到......
  • leetcode——数组算法——前缀和构建和应用
    leetcode——数组算法——前缀和构建和应用前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和303.区域和检索-数组不可变比如leetcode303.区域和(检索-数组不可变)题目介绍:给定一个整数数组nums,处理以下类型的多个查询:计算索引left和right(包含left......
  • 【算法】DFS
    DFSDFS是一种遍历或搜索图、树或图像等数据结构的算法,当然这个图、树未必存储下来。常见的是通过某种关系构造出的搜索树,搜索树一般是排列型搜索树和子集型搜索树。DFS一般使用栈或递归。一道模板题#include<bits/stdc++.h>usingnamespacestd;constintN=50;intn,m......
  • 基于NIQE算法的图像无参考质量评价算法matlab仿真
    1.算法运行效果图预览   2.算法运行软件版本MATLAB2022a  3.算法理论概述      NIQE(NaturalnessImageQualityEvaluator)算法是一种无参考图像质量评价算法,旨在评估图像的自然度,即图像看起来是否像自然场景。NIQE基于一组“质量感知”特征,并将其拟合到MV......
  • OpenCL规约算法例子
    本文给出一个规约算法求数组的和的例子。本例子求20000000(两千万)个整数的和。运算过程分成了两步,第一步是GPU对每一个工作组内规约求和,然后将每个工作组的求和结果放到数组中输出。第二步是对输出的数组用CPU求和。实际运行对比发现GPU的效率不如用CPU直接求和。下述算法运行环境......
  • 2024牛客寒假算法基础集训营3
    M题智乃的36倍数(normalversion)错解幂运算写成了乘~#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#defineintlonglong#definedebug(x)cout<<x<<""<<endl;#define_debug(a,n)for(inti=0;i<n;i++)......
  • 2024牛客寒假算法基础集训营1
    2024牛客寒假算法基础集训营1A解题思路:按照\(dfs\)出现顺序暴力判断即可。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=pair<ll,pai......
  • boruvka 算法学习笔记
    boruvka算法就是最小生成树B算法。B算法的思路是每次对每个连通块,求出它能连出去的权值最小的边,然后再按边权从小到大合并。由于每次操作连通块数至少减半,所以复杂度是\(O(m\logn)\)。1.CF1305GKuroniandAntihype题意:长为\(n\)的数列\(a\),现在要选择全部数,每一次你......
  • 微分积分及其运算法则成对列举
         ......
  • 【算法】排序
    冒泡排序思想:每一轮确定一个最大值移到最右边。点击查看代码for(inti=n;i>=1;i--){ for(intj=1;j<i;j++){ if(a[j]>a[j+1])swap(a[j],a[j+1]); } }选择排序思想:与冒泡相似。点击查看代码for(inti=n;i>=1;i--){ intmax_id......