小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 正文

解析动态规划问题(3)

2019年2月22日 812点热度 0人点赞 0条评论

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

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

问题分析

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

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

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

算法设计

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

  • 按照递归式计算第1个物品的处理情况,得到c[1][j],j=1,2,...,W;
  • 按照递归式计算第2个物品的处理情况,得到c[2][j],j=1,2,...,W;
  • 以此类推,按照递归式计算第n个物品的处理情况,得到c[n][j],j=1,2,...,W。

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

  • 首先i=n,j=W,如果c[i][j]>c[i-1][j],则说明第n个物品放入了购物车,令x[n]=1,j-=w[n];如果c[i][j]≤c[i-1][j],则说明第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

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

代码实现

#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(nW)
(2)空间复杂度O(n
W)
2.算法优化改进
使用一个数组dp[]保证第i次循环结束后dp[j]中表示的就是我们定义的c[i][j]。
所以代码如下:

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)

问题分析

递归表达式:
c[i][j]=0(j=i-1);
c[i][j]=min{c[i][k-1]+c[k+1][j]}+w[i][j](j≥i)
w[i][j]=qi-1(j=i-1);
w[i][j]=w[i][j-1]+pj+qj

算法设计

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

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

(4)构造最优解。

  • 首先读取s[1][n],令k=s[1][n],输出sk为最优二叉搜索树的根。
  • 判断如果k-1<1,表示虚结点ek-1是sk的左子树;否则,递归求解左子树Construct_Optimal_BST(1,k-1,1)。
  • 判断如果k≥n,表示虚结点ek是sk的右孩子。;否则,输出s[k+1][n]是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. 如何得到最优解递归式
    • 分析原问题最优解和子问题最优解的关系。
    • 考察有多少种选择。
    • 得到最优解递归式。
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 动态规划 算法
最后更新:2019年2月22日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
莱芜市2012年普通高中招生工作实施意见2 消防小提示 吴恩达深度学习课程DeepLearning.ai笔记(4-3) 《鸟哥的Linux私房菜》(基础篇)笔记整理(第7章)Part.2 Python chapter 8 learning notes 初中的最后一次执勤结束了。。。
标签聚合
python学习 算法 高中 Java 学习 鸟哥的linux私房菜 linux leetcode 生活 Python
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号