AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

算法笔记之动态规划（4）

2019-02-22 1575
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 用动态分析解决0-1背包问题有n个物品，每个物品的重量为w[i]，价值为v[i]，购物车容量为W。选若干个物品放入购物车，在不超过容量的前提下使获得的价值最大。问题分析（1）分析最优解的结构特征（2）建立具有最优值的递归式可以对每个物品依次检查是否放入或者不放入，对于第i个物品的处理状态：用ci表示前i件物品放入一个容量为j的购物车可以获得的最大价值。

用动态分析解决0-1背包问题

有n个物品，每个物品的重量为w[i]，价值为v[i]，购物车容量为W。选若干个物品放入购物车，在不超过容量的前提下使获得的价值最大。

问题分析

（1）分析最优解的结构特征
（2）建立具有最优值的递归式
可以对每个物品依次检查是否放入或者不放入，对于第i个物品的处理状态：用ci表示前i件物品放入一个容量为j的购物车可以获得的最大价值。

  • 不放入第i件物品，xi=0，装入购物车的价值不增加。那么问题就转化为“前i-1件物品放入容量为j的背包中”，最大价值为ci-1。
  • 放入第i件物品，xi=1，装入购物车的价值增加vi。

那么问题就转化为了“前i-1件物品放入容量为j-w[i]的购物车中”，此时能获得的最大价值就是ci-1]，再加上放入第i件物品获得的价值v[i]。即ci-1]+v[i]。
购物车容量不足，肯定不能放入；购物车容量组，我们要看放入、不放入哪种情况获得的价值更大。
所以，递归函数可以写为：
ci=ci-1（当ji）；
ci=max{ci-1]+v[i],ci-1}（当j>wi）

算法设计

（1）确定合适的数据结构
采用一维数组w[i]、v[i]分别记录第i个物品的重量和价值；二维数组用ci表示前i个物品放入一个容量为j的购物车可以获得的最大价值。
（2）初始化
初始化c[][]数组0行0列为0，其中i=01,2,...,n，j=0,1,2,...,W。
（3）循环阶段

  • 按照递归式计算第1个物品的处理情况，得到c1，j=1,2,...,W；
  • 按照递归式计算第2个物品的处理情况，得到c2，j=1,2,...,W；
  • 以此类推，按照递归式计算第n个物品的处理情况，得到cn，j=1,2,...,W。

（4）构造最优解
cn就是不超过购物车容量能放入物品的最大价值。如果还想知道具体放入了哪些物品，就需要根据c[][]数组逆向构造最优解，我们可以用一维数组x[i]来存储解向量。

  • 首先i=n，j=W，如果ci>ci-1，则说明第n个物品放入了购物车，令x[n]=1，j-=w[n]；如果ci≤ci-1，则说明第n个物品没有放入购物车，令x[n]=0.
  • i--，继续查找答案。
  • 直到i=1处理完毕。

图解

假设现在有5个物品，每个物品重量为（2,5,4,2,3），价值为（6,3,5,4,6），购物车容量为10。
c[][]如下表：

c[][] 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 6 6 6 6 6 6 6 6 6
2 0 0 6 6 6 6 6 9 9 9 9
3 0 0 6 6 6 6 11 11 11 11 11
4 0 0 6 6 10 10 11 11 15 15 15
5 0 0 6 6 10 12 12 16 16 17 17

所以最大价值为cn=17。
首先读取c5>c4，说明第5个物品装入了购物车，即x[5]=1，然后j=10-w[5]=10-3=7
然后去c4；
c4=c3，说明第4个物品没有装入购物车，即x[4]=0；
然后去找c3，依次类推。

代码实现

#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10000
#define M 105
int c[M][maxn];//c[i][j] 表示前i个物品放入容量为j购物车获得的最大价值
int w[M],v[M];//w[i] 表示第i个物品的重量，v[i] 表示第i个物品的价值
int x[M];  //x[i]表示第i个物品是否放入购物车
int main(){
    int i,j,n,W;//n表示n个物品，W表示购物车的容量
    cout << "请输入物品的个数 n:";
    cin >> n;
    cout << "请输入购物车的容量W:";
    cin >> W;
    cout << "请依次输入每个物品的重量w和价值v，用空格分开:";
    for(i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(i=1;i<=n;i++)//初始化第0列为0
        c[i][0]=0;
    for(j=1;j<=W;j++)//初始化第0行为0
        c[0][j]=0;
    for(i=1;i<= n;i++)//计算c[i][j]
        for(j=1;j<=W;j++)
            if(j<w[i])  //当物品的重量大于购物车的容量，则不放此物品
                c[i][j] = c[i-1][j];
            else    //否则比较此物品放与不放是否能使得购物车内的价值最大
                c[i][j] = max(c[i-1][j],c[i-1][j-w[i]] + v[i]);
    cout<<"装入购物车的最大价值为:"<<c[n][W]<<endl;

    //用于测试
    for (i=1; i<=n; i++ )
    {
        for (j=1; j<=W; j++ )
          cout << c[i][j]<<"\t" ;
        cout << endl;
    }
    cout << endl;

    //逆向构造最优解
    j=W;
    for(i=n;i>0;i--)
        if(c[i][j]>c[i-1][j])
        {
            x[i]=1;
            j-=w[i];
        }
        else
            x[i]=0;
    cout<<"装入购物车的物品序号为:";
    for(i=1;i<=n;i++)
        if(x[i]==1)
           cout<<i<<"  ";
    return 0;
}

算法分析及改进

1.算法复杂度分析
（1）时间复杂度：O(n*W)
（2）空间复杂度O(n*W)
2.算法优化改进
使用一个数组dp[]保证第i次循环结束后dp[j]中表示的就是我们定义的ci。
所以代码如下：

void opt1(int n,int W)
{
     for(i=1;i<=n;i++)
        for(j=W;j>0;j--)
            if(j>=w[i])  //当物品的重量大于购物车的容量，比较此物品放与不放是否能使得购物车内的价值最大
              dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}

我们可以缩小范围，因为只有当购物车的容量大于等于物品重量的时候才要更新，所以代码如下：

void opt2(int n,int W)
{
     for(i=1;i<= n;i++)
        for(j=W;j>=w[i];j--)
      //当物品的重量大于购物车的容量
 //比较此物品放与不放是否能使得购物车内的价值最大
           dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}

我们还可以再缩小范围，确定搜索的下界bound

void opt3(int n,int W)
{
     int sum[n];//sum[i]表示从1...i的物品重量之和
     sum[0]=0;
     for(i=1;i<=n;i++)
        sum[i]=sum[i-1]+w[i];
     for(i=1;i<=n;i++)
     {
         int bound=max(w[i],W-(sum[n]-sum[i-1]));
         //w[i]与剩余容量取最大值,
         //sum[n]-sum[i-1]表示从i...n的物品重量之和
         for(j=W;j>=bound;j--)
            //当物品的重量大于购物车的容量
            //比较此物品放与不放是否能使得购物车内的价值最大
           dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
     }
}

快速定位—最优二叉搜索树（OBST）

问题分析

递归表达式：
ci=0（j=i-1）；
ci=min{ci+ck+1}+wi（j≥i）
wi=qi-1（j=i-1）；
wi=wi+pj+qj

算法设计

（1）确定合适的数据结构
一维数组：p[]、q[]分别表示实结点和虚结点的搜索概率
二维数组：ci表示最优二叉搜索树T(i,j)的搜索成本，wi表示最优二叉搜索树T(i,j)中的所有实结点和虚结点的搜索概率之和，si表示最优二叉搜索树T(i,j)的根节点序号。
（2）初始化。ci=0.0，wi=q[i-1]，其中i=1,2,3,...,n+1。
（3）循环阶段。

  • 按照递归式计算元素规模是1的{si}（j=i）的最优二叉搜索树的搜索成本ci，并记录最优策略，即树根si，i=1,2,3,..,n。
  • 按照递归式计算元素规模是2的{si,si+1}（j=i）的最优二叉搜索树的搜索成本ci，并记录最优策略，即树根si，i=1,2,3,..,n-1。
  • 以此类推，直到求出所有元素{s1,s2,...,sn}的最优二叉搜索树的搜索成本c1和最优策略s1。

（4）构造最优解。

  • 首先读取s1，令k=s1，输出sk为最优二叉搜索树的根。
  • 判断如果k-1<1，表示虚结点ek-1是sk的左子树；否则，递归求解左子树Construct_Optimal_BST(1,k-1,1)。
  • 判断如果k≥n，表示虚结点ek是sk的右孩子。；否则，输出sk+1是sk的右孩子，递归求解右子树Construct_Optimal_BST(k+1,n,1)。
w[][] 0 1 2 3 4 5 6
1 0.06 0.18 0.37 0.52 0.59 0.76 1.00
2 0.08 0.27 0.42 0.49 0.66 0.90
3 0.10 0.25 0.32 0.49 0.73
4 0.07 0.14 0.31 0.55
5 0.05 0.22 0.46
6 0.05 0.29
7 0.10
c[][] 0 1 2 3 4 5 6
1 0 0.18 0.55 0.95 1.23 1.76 2.52
2 0 0.27 0.67 0.90 1.38 2.09
3 0 0.25 0.46 0.94 1.48
4 0 0.14 0.45 0.98
5 0 0.22 0.68
6 0 0.29
7 0
s[][] 0 1 2 3 4 5 6
1 1 2 2 2 3 5
2 2 2 3 3 5
3 3 3 3 5
4 4 5 5
5 5 6
6 6
7

代码实现

void Optimal_BST()
{
    for(i=1;i<=n+1;i++)
    {
        c[i][i-1]=0.0;
        w[i][i-1]=q[i-1];
    }
    for(int t=1;t<=n;t++)//t为关键字的规模
        //从下标为i开始的关键字到下标为j的关键字
        for(i=1;i<=n-t+1;i++)
        {
            j=i+t-1;
            w[i][j]=w[i][j-1]+p[j]+q[j];
            c[i][j]=c[i][i-1]+c[i+1][j];//初始化
            s[i][j]=i;//初始化
            //选取i+1到j之间的某个下标的关键字作为
            //从i到j的根，如果组成的树的期望值当前最小
            //则k为从i到j的根节点
            for(k=i+1;k<=j;k++)
            {
                double temp=c[i][k-1]+c[k+1][j];
                if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)
                //C++中浮点数因为精度问题不可以直接比较
                {
                    c[i][j]=temp;
                    s[i][j]=k;//k即为从下标i到j的根节点
                }
            }
            c[i][j]+=w[i][j];
        }
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
    if(flag==0)
    {
        cout<<"S"<<s[i][j]<<" 是根"<<endl;
        flag=1;
    }
    int k=s[i][j];
    //如果左子树是叶子
    if(k-1<i)
    {
        cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
    }
    //如果左子树不是叶子
    else
    {
        cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
        Construct_Optimal_BST(i,k-1,1);
    }
    //如果右子树是叶子
    if(k>=j)
    {
        cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
    }
    //如果右子树不是叶子
    else
    {
        cout<<"S"<<s[k+1][j]<<" is the right child of "<<"S"<<k<<endl;
        Construct_Optimal_BST(k+1,j,1);
    }
}

复杂度分析及改进

时间复杂度为O(n3)，空间复杂度为O(n2)。
又可以用四边形不等式优化（后续研究一下）
时间复杂度减少到O(n2)。

void Optimal_BST()
{
    for(i=1;i<=n+1;i++)
    {
        c[i][i-1]=0.0;
        w[i][i-1]=q[i-1];
    }
    for(int t=1;t<=n;t++)//t为关键字的规模
        //从下标为i开始的关键字到下标为j的关键字
        for(i=1;i<=n-t+1;i++)
        {
            j=i+t-1;
            w[i][j]=w[i][j-1]+p[j]+q[j];
            int i1=s[i][j-1]>i?s[i][j-1]:i;
            int j1=s[i+1][j]<j?s[i+1][j]:j;
            c[i][j]=c[i][i1-1]+c[i1+1][j];//初始化
            s[i][j]=i1;//初始化
            //选取i1+1到j1之间的某个下标的关键字
            //作为从i到j的根，如果组成的树的期望值当前
            //最小，则k为从i到j的根节点
            for(k=i1+1;k<=j1;k++)
            {
                double temp=c[i][k-1]+c[k+1][j];
                if(temp<c[i][j]&&fabs(temp-c[i][j])>1E-6)
                //C++中浮点数因为精度问题不可以直接比较
                {
                    c[i][j]=temp;
                    s[i][j]=k;//k即为从下标i到j的根节点
                }
            }
            c[i][j]+=w[i][j];
        }
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
    if(flag==0)
    {
        cout<<"S"<<s[i][j]<<" 是根"<<endl;
        flag=1;
    }
    int k=s[i][j];
    //如果左子树是叶子
    if(k-1<i)
    {
        cout<<"e"<<k-1<<" is the left child of "<<"S"<<k<<endl;
    }
    //如果左子树不是叶子
    else
    {
        cout<<"S"<<s[i][k-1]<<" is the left child of "<<"S"<<k<<endl;
        Construct_Optimal_BST(i,k-1,1);
    }
    //如果右子树是叶子
    if(k>=j)
    {
        cout<<"e"<<j<<" is the right child of "<<"S"<<k<<endl;
    }
    //如果右子树不是叶子
    else
    {
        cout<<"S"<<s[k+1][j]<<" is the right child of "<<"S"<<k<<endl;
        Construct_Optimal_BST(k+1,j,1);
    }
}

动态规划算法总结

动态规划关键总结如下：

  1. 最优子结构判定

    • 做出一个选择。
    • 假定已经知道了哪种选择是最优的。
    • 最优的会产生哪些子问题。
    • 证明原问题的最优解包含其子问题的最优解。

  2. 如何得到最优解递归式

    • 分析原问题最优解和子问题最优解的关系。
    • 考察有多少种选择。
    • 得到最优解递归式。
文章标签：
算法
JavaScript
C++
存储
关键词：
算法动态规划
算法笔记
算法笔记动态规划
真正的迪迦
目录
相关文章
众所周知
|
2月前
|
算法 开发者 Python
惊呆了！Python算法设计与分析，分治法、贪心、动态规划...这些你都会了吗？不会？那还不快来学！
【7月更文挑战第10天】探索编程巅峰，算法至关重要。Python以其易读性成为学习算法的首选。分治法，如归并排序，将大问题拆解；贪心算法，如找零问题，每步求局部最优；动态规划，如斐波那契数列，利用子问题解。通过示例代码，理解并掌握这些算法，提升编程技能，面对挑战更加从容。动手实践，体验算法的神奇力量吧！
众所周知
60 8
龙大吉
|
2月前
|
算法 Python
算法不再难！Python分治法、贪心、动态规划实战解析，轻松应对各种算法挑战！
【7月更文挑战第8天】掌握Python算法三剑客：分治、贪心、动态规划。分治如归并排序，将大问题拆解递归解决；贪心策略在每步选最优解，如高效找零；动态规划利用子问题解，避免重复计算，解决最长公共子序列问题。实例展示，助你轻松驾驭算法！**
龙大吉
51 3
热爱技术的小郑
|
1月前
|
机器学习/深度学习 算法 Java
算法设计（动态规划应用实验报告）实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法，包括它们的伪代码描述、Java源代码实现、时间效率分析，并展示了算法的测试用例结果，使读者对贪婪技术及其应用有了更深入的理解。
热爱技术的小郑
45 0
算法设计（动态规划应用实验报告）实现基于贪婪技术思想的Prim算法、Dijkstra算法
热爱技术的小郑
|
1月前
|
算法 Java 测试技术
算法设计（动态规划实验报告） 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法：解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法，并提供了它们的伪代码、Java源代码实现以及时间效率分析。
热爱技术的小郑
43 0
算法设计（动态规划实验报告） 基于动态规划的背包问题、Warshall算法和Floyd算法
土木林森
|
2月前
|
算法 Python
Python算法高手进阶指南：分治法、贪心算法、动态规划，掌握它们，算法难题迎刃而解！
【7月更文挑战第10天】探索Python算法的精华：分治法（如归并排序）、贪心策略（如找零钱问题）和动态规划（解复杂问题）。通过示例代码揭示它们如何优化问题解决，提升编程技能。掌握这些策略，攀登技术巅峰。
土木林森
62 2
众所周知
|
2月前
|
算法 程序员 Python
算法小白到大神的蜕变之路：Python分治法、贪心、动态规划，一步步带你走向算法巅峰！
【7月更文挑战第9天】探索算法之旅，以Python解锁编程高手之路。分治法如二分查找，将复杂问题拆解；贪心算法解决活动选择，每次选取局部最优；动态规划求斐波那契数列，避免重复计算，实现全局最优。每一步学习，都是编程能力的升华，助你应对复杂挑战，迈向算法大师！
众所周知
35 1
龙大吉
|
2月前
|
存储 算法 Python
Python算法界的秘密武器：分治法巧解难题，贪心算法快速决策，动态规划优化未来！
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解，如归并排序；贪心算法每步选局部最优解，不保证全局最优，如找零钱；动态规划存储子问题解求全局最优，如斐波那契数列。选择合适算法能提升编程效率。
龙大吉
49 1
东方睿赢
|
2月前
|
存储 算法 Python
震撼！Python算法设计与分析，分治法、贪心、动态规划...这些经典算法如何改变你的编程世界！
【7月更文挑战第9天】在Python的算法天地，分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序，将大问题拆解为小部分解决；贪心算法以局部最优求全局，如Prim的最小生成树；动态规划通过存储子问题解避免重复计算，如斐波那契数列。掌握这些，将重塑你的编程思维，点亮技术之路。
东方睿赢
51 1
土木林森
|
2月前
|
存储 算法 大数据
Python算法高手的必修课：深入理解分治法、贪心算法、动态规划，让你的代码更智能！
【7月更文挑战第9天】在Python算法学习中，分治法（如归并排序）将大问题分解为小部分递归解决；贪心算法（如货币找零）在每步选择局部最优解尝试达到全局最优；动态规划（如斐波那契数列）通过存储子问题解避免重复计算，解决重叠子问题。掌握这三种方法能提升代码效率，解决复杂问题。
土木林森
35 1
东方睿赢
|
2月前
|
算法 索引 Python
逆袭算法界！Python分治法、贪心算法、动态规划深度剖析，带你走出算法迷宫！
【7月更文挑战第8天】分治法，如快速排序，将大问题分解并合并解；贪心算法，选择局部最优解，如活动选择；动态规划，利用最优子结构避免重复计算，如斐波那契数列。Python示例展示这些算法如何解决实际问题，助你精通算法，勇闯迷宫。
东方睿赢
30 1

热门文章

最新文章

  • 1
    深度 ｜ 大数据算法应用的测试发展之路
  • 2
    数据结构与算法(三) 线性表之双向链表
  • 3
    算法学习之路|人口普查
  • 4
    《数字视频和高清：算法和接口》一1.11幅型比的比较
  • 5
    《推荐系统：技术、评估及高效算法》一3.1　简介
  • 6
    机器学习算法：补一个k-近邻算法的测试
  • 7
    日期不能交叉的检测算法
  • 8
    【机器学习算法-python实现】svm支持向量机(1)—理论知识介绍
  • 9
    建模：产品(Application)积分算法
  • 10
    限制程序中某类操作的执行次数的算法设计及C代码实现
  • 1
    使用Java编写高效的内存管理算法
    21
  • 2
    前端 JS 经典：LRU 缓存算法
    35
  • 3
    FPGA强化（10）：基于Sobel算法的边缘检测（一）
    22
  • 4
    揭开JavaScript字符串搜索的秘密：indexOf、includes与KMP算法
    71
  • 5
    算法 —— 滑动窗口
    27
  • 6
    算法——Prim算法
    32
  • 7
    算法——Dijkstra算法
    32
  • 8
    算法——BST
    28
  • 9
    算法——BFS
    26
  • 10
    算法——DFS
    45

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    搭建自己的私有云盘工具总结