美文网首页
动态规划算法

动态规划算法

作者: TomyZhang | 来源:发表于2019-05-26 16:38 被阅读0次

一、概念

动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
比较有趣的一句话是:每个动态规划都从一个网格开始。

问题 ==> 子问题 ==> 子问题最优解 ==> 问题最优解

二、思路

1.分析最优解的性质,并刻画其结构特征。
2.递归的定义最优解。
3.以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值。
4.根据计算最优值时得到的信息,构造问题的最优解。

三、特性

  • 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
  • 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
  • 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

四、应用

0-1背包问题

题目:
给定n种物品和一个背包,物品i的重量为wi,价值为vi,背包的容量为c。问:应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

分析:
0-1背包问题

代码:

#include<stdio.h>
#define MAX 100

int n;              // 描述物品个数
int c;              // 描述背包容量
int value[MAX];     // 描述物品价值
int weight[MAX];    // 描述物品重量

int main() {
    // 初始赋值操作
    value[0] = 1500;
    value[1] = 3000;
    value[2] = 2000;
    weight[0] = 1;
    weight[1] = 4;
    weight[2] = 3; 
    c = 4;
    n = 3;

    // 构造最优解的网格:3行4列
    int maxValue[MAX][MAX];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < c; j++) {
            maxValue[i][j] = 0;
        }
    }   // end for

    // 填充网格
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= c; j++) {
            if (i == 0) {
                maxValue[i][j - 1] = (weight[i] <= j ? value[i] : 0);
            } else {
                int topValue = maxValue[i - 1][j - 1];  // 上一个网格的值
                int thisValue = (weight[i] <= j ?       // 当前商品的价值 + 剩余空间的价值
                        (j - weight[i] > 0 ? value[i] + maxValue[i - 1][j - weight[i]] : value[i])
                        : topValue);

                // 返回 topValue和thisValue中较大的一个
                maxValue[i][j - 1] = (topValue > thisValue ? topValue : thisValue);
            }   // end if
        }   // end inner for
    }   // end outer for

    // 打印结果二维数组maxValue
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < c; j++) {
            printf("%6d", maxValue[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

相关文章

  • 动态规划算法

    动态规划算法 最长上升子序列

  • 维特比算法

    维特比(Viterbi)算法是一种动态规划算法,在处理隐马尔可夫(HMM)最优路径问题时经常被使用. 动态规划算法...

  • 最短路径解决方法

    Floyd算法;Dijkstra算法;Bellman-Ford算法;动态规划算法

  • 背包问题

    介绍 学习动态规划算法的经典例题。动态规划算法一般有3个特征1、最优化原理:最优解所包含的子问题的解也是最优的。2...

  • 动态规划算法(01背包问题)

    一. 动态规划算法介绍: 动态规划算法和分治算法类似,也是将待求解问题分成若干个小问题一步步求解,不同的是,每一个...

  • 基础算法

    二分查找 冒泡排序(优化) 归并排序 动态规划算法

  • 动态规划入门

    1.什么是动态规划动态规划是在前面已有答案的基础上向下递推的过程 动态规划算法的两种形式上面已经知道动态规划算法的...

  • 【JS算法】动态规划 - 斐波那契数列

    动态规划算法 动态规划算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。其基本思想也...

  • 2019-11-04 回溯算法

    package others; import java.util.Arrays; /** 动态规划算法计算10个工...

  • 动态规划

    动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...

网友评论

      本文标题:动态规划算法

      本文链接:https://www.haomeiwen.com/subject/erkftctx.html