算法设计与分析复习--动态规划

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

上一篇

算法设计与分析复习–递归与分治(二)

动态规划性质

与分析法类似:将原问题分解为子问题
不同点:不是通过递归的方式,而是自底向上的求解问题
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

矩阵连乘问题

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
矩阵连乘的次数是左矩阵行列,右矩阵行列取出左右中进行相乘。
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
由于矩阵乘积需要满足左矩阵列等于右矩阵的行,所以可以用一维数组进行存n个矩阵,共n + 1个元素,从第一个矩阵的(1)行(2)列,第二个矩阵由于行与第一个的列相同就不在重复存储所以只需存第二个的(3)列,一次类推

数据结构:
a[N] 存矩阵行列
dp[N][N] => dp[i][j]表示第i个矩阵到第j个矩阵的最小连乘次数

因为是从小到大算每个区间内的最小值=> 区间dp

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

const int N = 110;

int a[N], dp[N][N], n;

void out()
{
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
            printf("%d ", dp[i][j]);
        puts("");
    }
}

int main()
{
    scanf("%d", &n);
    
    for (int i = 0; i <= n; i++) scanf("%d", &a[i]);

    // 初始化dp数组
    memset(dp, 0, sizeof(dp));

    for(int len = 2; len <= n; len ++)
    {
        for (int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;
            dp[i][j] = 1e8; // 初始化为一个较大的值

            for (int k = i; k < j; k ++)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j]);
                // out();
            }
        }
    }
    out();
    printf("%d\n", dp[1][n]);
    return 0;
}

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

区间DP类似题目 AcWing.282石子合并

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

凸多边形最优三角部分

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
问题描述
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
可以转换成矩阵连乘问题
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
加完括号的形式就是那个最优三角形的位置

数据结构
v[N]: 表示每个结点对应值
dp[N][N]: dp[i][j]表示结点从 i 到 j 的三角的权重,取min
状态计算(区间dp):
d p [ i ] [ j ] = m i n { d p [ i ] [ k ] + d p [ k + 1 ] + w ( v i − 1 v k v j ) } dp[i][j] = min\{ dp[i][k] + dp[k + 1] + w(v_{i-1}v_kv_j)\} dp[i][j]=min{dp[i][k]+dp[k+1]+w(vi1vkvj)}

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

最长公共子序列

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

AcWing897.最长公共子序列

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

char a[N], b[N];
int dp[N][N], n, m;
int x[N][N];//寻路数组
vector<char> ans;

void out()
{
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
            cout << dp[i][j] << ' ';
        cout << endl;
    }
    cout << "*****************" << endl;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
            cout << x[i][j] << ' ';
        cout << endl;
    }
    cout << "*****************" << endl;
}

void trackback(int i, int j)
{
    if (i <= 0 || j <= 0) return;
    if (x[i][j] == 1){
        ans.push_back(a[i]);
        trackback(i - 1, j - 1);
    } 
    else if (x[i][j] == 2) trackback(i - 1, j);
    else trackback(i, j - 1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    cin >> a + 1 >> b + 1;//因为有i - 1操作所以起始下标要从1开始防止数组越界
    
    for(int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if(a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                x[i][j] = 1;// 1表示i和j都要选为对应公共元素
            }
            else if(dp[i - 1][j] >= dp[i][j - 1]){
                dp[i][j] = dp[i - 1][j];
                x[i][j] = 2;//回溯沿着表上走
            }
            else{
                dp[i][j] = dp[i][j - 1];
                x[i][j] = 3;//沿着表左走
            }
        }
    }
    out();
    cout << dp[n][m] << endl;
    trackback(n, m);
    reverse(ans.begin(), ans.end());//答案顺序反了,需要翻转一下
    for (auto i : ans)
        cout << i;
    return 0;
}

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
输入顺序写反了,列是第一个序列,行时第二个序列
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

0-1背包问题

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

AcWing2. 01背包

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int dp[N][N], w[N], v[N], n, c;

int main()
{
    scanf("%d%d", &n, &c);
    
    for (int i = 1; i <= n; i ++) scanf("%d%d", &w[i], &v[i]);
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= c; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if(w[i] <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }
    
    printf("%d", dp[n][c]);
    return 0;
}

观察发现状态计算的方程中只用到了第i行和第i - 1行,所以可以用滚动数组,将这个二维数组优化成一维数组
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int dp[N], w[N], v[N], n, c;

int main()
{
    scanf("%d%d", &n, &c);
    
    for (int i = 1; i <= n; i ++) scanf("%d%d", &w[i], &v[i]);
    
    for (int i = 1; i <= n; i ++)
        for (int j = c; j >= 1; j --)// 也可以将下面if条件拿到上面=> for(int j = c; j >= w[i]; j --)
        {
            if(w[i] <= j) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    
    printf("%d", dp[c]);
    return 0;
}

带结果回溯的写法
如果用回滚数组就找不到对应物品的坐标了,但是可以找到对应价值的物品

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int dp[N][N], w[N], v[N], n, c;
int x[N][N];

void out()
{
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= c; j ++)
            printf("%d ", dp[i][j]);
        puts("");
    }
    puts("************");
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= c; j ++)
            printf("%d ", x[i][j]);
        puts("");
    }
    puts("************");
}

void trackback(int i, int j, int f)
{
    if(i <= 0 || j <= 0) return;
    if(f == 0){
        printf("不选第%d件商品\n", i);
        trackback(i - 1, j, x[i - 1][j]);
    }
    if(f == 1){
        printf("选第%d件商品\n", i);
        trackback(i - 1, j - w[i], x[i - 1][j - w[i]]);//选这件商品后的坐标需要算一下
    }
}

int main()
{
    scanf("%d%d", &n, &c);
    
    for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= c; j ++){
            if(w[i] <= j && dp[i - 1][j] < dp[i - 1][j - w[i]] + v[i]){
                dp[i][j] = dp[i - 1][j - w[i]] + v[i];
                x[i][j] = 1;
            }
            else{
                dp[i][j] = dp[i - 1][j];
                x[i][j] = 0;
            }
        }
    out();
    printf("%d\n", dp[n][c]);
    trackback(n, c, x[n][c]);
    return 0;
}

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

图像压缩

像素点灰度值序列{ p 1 p_1 p1, p 2 p_2 p2, … p n p_n pn}表示图像。
不同定长图像每一位为8个bit
但是可以将灰度值存在变长字节中
但是变长存储解药进行解码,所以要存储解码信息,第 i i i 端存了多少位要用几位二进制来存。
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
较小值用较小的bit来存,较大值用较长bit来存。但是解压缩要花的bit是固定的
11 ∗ m    b i t 是解压缩固定的 b i t ( m 表示划分成几段 ) 11 * m\ \ bit是解压缩固定的bit(m表示划分成几段) 11m  bit是解压缩固定的bit(m表示划分成几段)

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

数据结构:
a [ i ] a[i] a[i] 表示每个像素所占位数
l [ i ] l[i] l[i] 表示划分的第 i i i 段有 l [ i ] l[i] l[i] 个像素
b [ i ] b[i] b[i] 表示划分的第 i i i 段用 b [ i ] b[i] b[i] 位表示

其中一种划分方式
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划
s [ i ] s[i] s[i]就是上面分析的 d p [ i ] dp[i] dp[i]
算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int a[N], s[N], n;
int l[N], b[N];//当前分组a[i]和前面共几个为一段,比特多少
void out()
{
    printf("a[i] : ");
    for (int i = 1; i <= n; i ++)
        printf("%d ", a[i]);
    puts("");
    
    printf("s[i] : ");
    for (int i = 1; i <= n; i ++)
        printf("%d ", s[i]);
    puts("");
    
    printf("l[i] : ");
    for (int i = 1; i <= n; i ++)
        printf("%d ", l[i]);
    puts("");
    
    printf("b[i] : ");
    for (int i = 1; i <= n; i ++)
        printf("%d ", b[i]);
    puts("");
}

int get_max(int ed, int step)
{
    int m = 0, i = ed;
    while(step)
    {
        m = max(m, a[i]);
        i --;
        step --;
    }
    return m;
}

int main()
{
    memset(s, 0x3f, sizeof s);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++){
        int p;
        scanf("%d", &p);
        int t = 0;
        while (p) t ++, p /= 2;
        a[i] = t;
    }
    
    s[0] = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            int maxa = get_max(i, j);
            if(s[i - j] + j * maxa + 11 < s[i])
            {
                l[i] = j;
                b[i] = maxa;
                s[i] = s[i - j] + j * maxa + 11;
            }
        }
    printf("最优压缩位数:%d\n", s[n]);
    out();
    return 0;
}

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

算法设计与分析复习--动态规划,矿大往事,算法设计与分析,算法,动态规划

下一篇

算法设计与分析复习–贪心(一)文章来源地址https://www.toymoban.com/news/detail-756926.html

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

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

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

相关文章

  • 【算法分析与设计】动态规划(上)

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

    2024年02月08日
    浏览(42)
  • 算法设计与分析实验---动态规划

    任务描述 沿着河岸摆放 N 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 2 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 例如: 4 堆石子 4,5,9,4 ,可以按 (((4,5),9),4) 合并。 第一次合并得分是 9 分,合并之后石子堆是 9,9,4 第二次合并得

    2024年02月08日
    浏览(47)
  • 算法设计与分析 实验三 动态规划

    1.打家劫舍:  给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 入: 每组测试案例有两行,第一行只有一个整数N,代表着有N间房屋 第二行有N个整数,代表着每间房屋里的金额,金额范围[0, 1000]。 出:

    2024年01月24日
    浏览(75)
  • 【算法设计与分析】作业2:动态规划

    最长递增⼦序列(LIS) 编程实现求解最长递增⼦序列的三种动态规划算法(⼀些细节请参考课件) 1.1 算法1:令 L ( k ) L(k) L ( k ) 表示 s [ 1.. n ] s[1..n] s [ 1.. n ] 中以 s [ k ] s[k] s [ k ] 结尾的LIS的长度,原问题即求解 max ⁡ 1 ≤ k ≤ n L ( k ) max_{1le kle n}L(k) max 1 ≤ k ≤ n ​ L ( k

    2024年02月21日
    浏览(40)
  • 算法设计与分析实验:动态规划与贪心

    目录 一、零钱兑换 1.1 思路一:动态规划 1.2 思路二:贪心 二、安排工作以达到最大效益 2.1 具体思路 2.2 思路呈现 2.3 代码实现 2.4 复杂度分析 2.5 运行结果 三、雇佣k名工人的最低成本 3.1 具体思路 3.2 思路展示 3.3 代码实现 3.4 复杂度分析 3.5 运行结果 结尾语 “生活有意思的

    2024年02月19日
    浏览(64)
  • 【动态规划】01背包问题——算法设计与分析

    若超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走,则如何选择可以使得收益最高? 商品 价格 体积 啤酒 24 10 汽水 2 3 饼干 9 4 面包 10 5 牛奶 9 4 0-1 Knapsack Problem 输入: quad - n n n 个商品组成集合 O O O ,每个商品有属性价格 p i p_i p i ​ 和体积 v i v_i v

    2024年02月04日
    浏览(75)
  • 【算法设计与分析】动态规划-练习题

    输入一个整数数组 S[n] ,计算其最长递增子序列的长度,及其最长递增子序列。 定义 k ( 1 ≤ k ≤ n ) k (1 ≤ k ≤ n) k ( 1 ≤ k ≤ n ) ,L[k]表示以 S[k] 结尾的递增子序列的最大长度。子问题即为 L[k]。 对于每一个k,我们都遍历前面0~k-1的所有的数,找出最大的L[i],且 S [ k ] L [

    2024年02月03日
    浏览(57)
  • 【算法设计与分析】动态规划:数塔问题

    提示:头歌 算法作业 实验七 动态规划 第1关:数塔问题 本关任务:编写用动态规划解决数塔问题。 求解过程(自底向上) 决策结果输出过程(自顶向下) 将上述分析求解过程角标记录为 path数组 ,方便顺序输出结果 代码如下(不知题目给出三维数组的a的第三维我用处,去

    2024年02月11日
    浏览(69)
  • 【动态规划】矩阵链乘法——算法设计与分析

    对于矩阵 U p × q U_{ptimes q} U p × q ​ 和 V q × r V_{qtimes r} V q × r ​ , Z p × r = U V Z_{ptimes r}=UV Z p × r ​ = U V ,共需计算 p q r pqr pq r 次标量乘法,时间复杂度为 Θ ( p q r ) Theta (pqr) Θ ( pq r ) 矩阵乘法满足结合律,即 ( U V ) W = U ( V W ) (UV)W=U(VW) ( U V ) W = U ( VW ) ,选择不同的结合

    2024年02月03日
    浏览(61)
  • 算法分析与设计——动态规划求解01背包问题

    假设有四个物品,如下图,背包总容量为8,求背包装入哪些物品时累计的价值最多。 我们使用动态规划来解决这个问题,首先使用一个表格来模拟整个算法的过程。 表格中的信息表示 指定情况下能产生的最大价值 。例如, (4, 8)表示在背包容量为8的情况下,前四个物品的最

    2024年02月04日
    浏览(66)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包