算法设计与分析 | 动态规划

发布时间:2023年12月25日

算法简介

动态规划(Dynamic Programming,简称DP)是一种通过把原问题分解为相互重叠的子问题,并仅仅解决每个子问题一次,将其解保存在一个表格中,从而避免重复计算,提高效率的算法思想。

动态规划的基本思想可以概括为以下几个步骤:

  1. 划分子问题: 将原问题划分为若干个规模较小的子问题。

  2. 解决子问题: 递归地或迭代地求解子问题。通常,通过保存子问题的解避免重复计算。

  3. 合并子问题的解: 将子问题的解组合起来,得到原问题的解。

同时,在使用动态规划时,需注意问题的以下两个性质

  1. 重叠子问题(Overlapping Subproblems): 原问题可以分解为若干个相同的子问题。解决这些子问题只需要一次计算,并将结果存储以避免重复计算。

  2. 最优子结构(Optimal Substructure): 问题的最优解可以通过子问题的最优解推导出。

例题两道

1. 0-1背包问题

问题描述:有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。第 i 件物品的体积是 v_i,价值是 w_i。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。

题解:

初始化f数组的第i行第j列为背包容量为j的情况下在前i件物品中可装入的最大价值,对背包容量(列)进行遍历,对物品(行)进行动态规划,具体如下:

  • 若j大于当前物品容量,则选择是否加入此物品;
  • 否则,不能加入此物品;

时间复杂度为O(n×v),c++代码如下:

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n, v;
    cin >> n >> v;
    int volume[n], money[n];
    int f[n+1][v+1] = {0};
    for(int i = 1; i <= n; i++)
        cin >> volume[i] >> money[i];
    int value = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= v; j++) {
            if(j >= volume[i]) 
                f[i][j] = max(f[i-1][j], f[i-1][j-volume[i]] + money[i]);
            else
                f[i][j] = f[i-1][j];
        }
    cout << f[n][v] << endl;
    return 0;
}

2. 最大子矩形问题

问题描述:给定一个包含整数的二维矩阵,子矩形是位于整个阵列内的任何大小为 1×1或更大的连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中,具有最大和的子矩形被称为最大子矩形。

题解:

初始化sum数组的第i行第j列为二维矩阵第i行第0位到第j位的和sum[i][j] = sum[i][j-1] + matrix[i][j],对列进行遍历,对行进行动态规划,具体如下:

  • k、j为列标,表示遍历(k,j)列的内容;
  • i为行标,表示是否加上第i行第(k,j)列的和;

最后取最大值即可,时间复杂度为O(n^3),c++代码如下:

#include<bits/stdc++.h>

using namespace std;
int main(){
    int n;
    cin >> n;
    int matrix[n+1][n+1], sum[n+1][n+1] = {0};
    for(int i = 1; i < n+1; i++)
        for(int j = 1; j < n+1; j++){
            cin >> matrix[i][j];
            sum[i][j] = sum[i][j-1] + matrix[i][j];
        }
    int ans = -1000;
    for(int j = 1; j <= n ; j++)
        for(int k = 0; k < j; k++){
            int temp = 0;
            for(int i = 1; i <= n; i++){
                temp = max(sum[i][j] - sum[i][k], temp + sum[i][j] - sum[i][k]);
                ans = max(ans,temp);
            }
        }
    cout<<ans<<endl;
    return 0;     
}

文章来源:https://blog.csdn.net/m0_62249876/article/details/135175744
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。