最详细动态规划解析——背包问题

最详细动态规划解析——背包问题动态规划的定义要解决一个复杂的问题,可以考虑先解决其子问题。这便是典型的递归思想,比如最著名的斐波那契数列,讲递归必举的例子。斐波纳契数列的定义如下:F(0)=1,F(1)=1,F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)用递归可以很快写出这样一个函数,咋一看真牛逼,几行代码就搞定了intfib(inti){if(i<=1){ret

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

动态规划的定义

要解决一个复杂的问题,可以考虑先解决其子问题。这便是典型的递归思想,比如最著名的斐波那契数列,讲递归必举的例子。

斐波纳契数列的定义如下:F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
用递归可以很快写出这样一个函数,咋一看真牛逼,几行代码就搞定了

int fib(int i)
{
    if(i <= 1)
    {
        return 0;
    }
    return fib(i - 1) + fib(i - 2);
}

将该函数的执行过程用图表示出来,就会发现fib4执行了一次,fib3执行了两次,fib2执行了三次,fib1计算了5次,重复的次数呈现爆发增长,接近与指数级。如果n取得足够大,暂且不说费时的问题,直接就会因为递归次数太多,函数堆栈溢出而程序奔溃。
image

那么很快就有人想到,用一个数组来保存曾经计算过的数据来避免重复计算。这种思想便是动态规划
我们来实现一下

#include <iostream>
#include <stdlib.h>
#include <vector>

using namespace std;

int fib(int n, vector<int>& vec);

int main(int argc, char** argv)
{
        if(argc != 2)
        {
                cout << "usage: ./a.out number" << endl;
        }
        int num = atoi(argv[1]);

        vector<int> vec(num + 1, -1);

        int ret = fib(num, vec);

        cout << "fib(" << argv[1] << ")" << " = " << ret << endl;
        return 0;
}

int fib(int n, vector<int>& vec)
{
        if(n <= 1)
        {
                return 1;
        }

        if(vec[n] == -1)
        {
                vec[n] = fib(n - 1, vec) + fib(n - 2, vec);
        }
        return vec[n];
}

当然,对于递归问题也可以转化为循环来解决。

#include <iostream>
#include <stdlib.h>

using namespace std;

int fib(int n);

int main(int argc, char** argv)
{
        if(argc != 2)
        {
                cout << "usage: ./a.out number" << endl;
        }

        int ret = fib(atoi(argv[1]));
        cout << "fib(" << argv[1] << ")" << " = " << ret << endl;
        return 0;
}


int fib(int n)
{
        if(n <= 1)
        {
                return 1;
        }

        int n1 = 1;
        int n2 = 1;

        for(int i = 1; i < n; ++i)
        {
                int temp = n1;
                n1 = n1 + n2;
                n2 = temp;
        }

        return n1;
}

背包问题

现在我们来看一个复杂的问题,讲动态规划必须谈到的背包问题,如果理解了此方法,那么对于同一类型的问题都可以用类似的方法来解决,学算法最重要的是学会举一反三。背包问题分为01背包问题和完全背包问题,背包问题用知乎某答主的话讲就是:一个小偷背了一个背包潜进了金店,包就那么大,他如果保证他背出来所有物品加起来的价值最大。

01背包问题的描述:有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?

要说明这个问题,要先了解一下背包问题的状态转换方程: f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }

其中:
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。
Pi表示第i件物品的价值。

初学者最不懂的地方可能就是这个状态方程了,i是什么鬼,j又是什么鬼?下面具体来说这个状态方程怎么来的。
之前说过动态规划是考虑递归的思想,要解决这个问题,首先想到解决其子问题。
要从5个中选出若干个装入容量为10的背包,可以分解为,将a物品装入背包,然后从其他四个中选出若干个装入剩余容量为8的袋子,因为a已经占去了2个位置;或者不装a,从其他四个中选出若干个装入容量为10的袋子?这两种做法中,价值最大的就是我们需要的方案。如果选择了第一种方案,那么继续分解,将b物品装入袋子,从其余三个中选出若干个装入剩余容量为6的袋子,或者不装b(也许你更乐意装b),从剩余三个中选出若干个装入剩余容量为8的袋子,选择这两种方案中价值最大的。依次类推,直到五个物品都选择完毕。将其一般化,用i代替a,用j代替10,用数学公式表达出来就是上面那个公式了,是不是觉得已经看懂了这个公式。
上面公式中还有个( j >= Wi ),表示剩余的容量至少要大于该物品的重量,才需要讨论装不装的问题。
既然子问题已经解决,那么自然想到用递归了,我们用递归来实现

#include <iostream>
#include <vector>

using namespace std;

vector<char> things = {
  
  'a', 'b', 'c', 'd', 'e'};
vector<int> value = {
  
  6, 3, 5, 4, 6};
vector<int> weight = {
  
  2, 2, 6, 5, 4};

int backpack(int n, int w)
{
    if(n == 0 | w == 0)
    {
        return 0;
    }

    int ret;

    if(w < weight[5 - n])
    {
        ret = backpack(n - 1, w);
        cout << "n = " << n << " w = " << w << " val = " << ret << endl;
        return ret;
    }

    //n表示从多少件物品中选
    //刚开始可以从五件物品中选,然后就是两种情况,放入第一件还是不放入第一件
    //第一件选择完毕后,就需要从其余四件中选择,重复上面的过程
    //
    //当n=5时,5-n表示第一件,n=4时候,5-n表示第二件
    int val1 = backpack(n - 1, w - weight[5 - n]) + value[5 - n];
    int val2 = backpack(n - 1, w);

    if(val1 > val2)
    {
        ret = val1;
        //cout << "选择物品" << things[5 - n] << endl;
    }
    else if(val1 < val2)
    {
        ret = val2;
        //cout << "不选择物品" << things[5 - n] << endl;
    }
    else
    {
        ret = val1;
        //cout << "拿不拿" << things[5 - n] << "一样" << endl;
    }

    cout << "n = " << n << " w = " << w << " val = " << ret << endl;
    return ret;
}

int main()
{
    int ret = backpack(5, 10);
    cout << "max value = " << ret << endl;
    return 0;
}
//输出结果
n = 1   w = 1   val = 0
n = 1   w = 6   val = 6
n = 2   w = 6   val = 6
n = 3   w = 6   val = 6
n = 1   w = 2   val = 0
n = 2   w = 2   val = 0
n = 1   w = 3   val = 0
n = 1   w = 8   val = 6
n = 2   w = 8   val = 6
n = 3   w = 8   val = 6
n = 4   w = 8   val = 9
n = 1   w = 2   val = 0
n = 2   w = 2   val = 0
n = 1   w = 3   val = 0
n = 1   w = 8   val = 6
n = 2   w = 8   val = 6
n = 3   w = 8   val = 6
n = 1   w = 4   val = 6
n = 2   w = 4   val = 6
n = 1   w = 5   val = 6
n = 1   w = 10   val = 6
n = 2   w = 10   val = 10
n = 3   w = 10   val = 11
n = 4   w = 10   val = 11
n = 5   w = 10   val = 15
max value = 15

递归的过程是怎样的呢?
这里写图片描述

同样出现与求斐波那契数列相同的问题,有重复计算的地方。同样的,采取用数组来保存结果,这个结果就是上面那个表,显然我们要用一个二维数组才能完成该工作。可以采取,与之前相同的方法,在递归里加数组,但是这次我们换一种方式,用循环来做。

对于用循环来解文献2采用的列表方法非常有助于理解,因此我们采用其方法来讲述,不同的是我们会将这个表生成的过程进行详细阐述。下面这个表就是文献2中用来讲述背包问题的表,大家可以先考虑一下这个表示怎么生成的。
这里写图片描述

为了便于描述,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e可以选择了,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。对于d2单元格,表示只有物品e,d可以选择时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。所以这个表列上的数字表示背包目前的容量,该行以及该行以下的物品是可以选择的,而该行以上的物品则不是该行可以选择的。这个表是从下往上、从左往右生成的。

以第4列为例分析一下生成过程:e4用公式表示就是f[1, 4] = max{(f[0, 4 – 4] + 6), f[0, 4]},对于d4用公式表示就是f[2, 4] = max{f[1, 4]}(因为容量为4的背包装不下重量为5的d物体),同理c4=f[3, 4]=max{f[2, 4]},b4 = f[4, 4] = max{(f[3, 4 – 2] + 3), f[3, 4]}

/************************************************************************/
/* 01背包问题 ** 问题描述:有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和? /************************************************************************/
#include <tchar.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <cstdlib>

using namespace std;

int weight[5] = {
  
  2, 2, 6, 5, 4};   //每个物品的重量
int value[5] = {
  
  6, 3, 5, 4, 6};      //每个物品的价值
int C[6][11];   //保存各种情况能装下物品价值的数组

vector<int> path;

void FindAnswer()
{
    int capacity = 10;
    for (int i = 5; i > 0; --i)
    {
        if (C[i][capacity] > C[i - 1][capacity])
        {
            path.push_back(i);
            capacity -= weight[i - 1];
        }
    }
}

void Package()
{
    for (int i = 0; i < 11; i++)
    {
        for (int j = 0; j <6; ++j)
        {
            if (i == 0)
            {
                //可选物品为0,所以能装的价值只能为0
                C[j][i] = 0;
            }
            else if (j == 0)
            {
                //容量为零,所以能装的价值也是0
                C[j][i] = 0;
            }
            else
            {
                //判断当前容量能放入
                if (i >= weight[j - 1])
                {
                    C[j][i] =  max(C[j - 1][i], (C[j -1][i - weight[j - 1]] + value[j - 1]) );
                }
                //如果不能放入,则不放入该物品
                else
                {
                    C[j][i] = C[j - 1][i];
                }
            }           
        }
    }
}

int _tmain(int args, TCHAR* argv[])
{
    memset(C, -1, sizeof(C));
    Package();
    FindAnswer();
    return 0;
}

举一反三

动态规划来解决类似问题,大家可以试试:
硬币找零问题
金字塔最大路径问题

参考文献:

  1. http://baike.baidu.com/link?url=VaCiaDEjRqYPB433OJrlR8NluEuiKUYol1w9yGEzzzPsVkEKG9iKEIIgArEsbEmuiyJ-H12FFuFPQVJMaxbXYArPgpHx5kzfUSU48tJ4OBRhdf2_T2LAkVDAG-wx64Ad2Cl9sLVQHt3QuISVPip_Da
  2. http://blog.csdn.net/mu399/article/details/7722810
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164396.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 2021最新Java零基础自学教程,java从入门到精通

    2021最新Java零基础自学教程,java从入门到精通Java是一门用途广泛的语言,不但可以用来开发网站后台、PC客户端和AndroidAPP,还在数据分析、网络爬虫、云计算领域大显身手。从学术的角度讲,Java是一门面向对象的编程语言,初学者需要花费不少时间来熟悉面向对象的概念、语法和编程思想,有不理解的地方请一定要坚持,多花时间编写代码自然会豁然开朗。只有一步一个脚印,踏踏实实学习,才能从零基础到入门,再到精通。大家在学习的过程中也要多看几套Java教程,不要死啃一本书,这样才能才能博采众长,进步更快。今天分享的也是我在自

  • 13款国内外知名PHP集成环境的优缺点分析,PHP集成环境推荐、PHP绿色集成环境推荐「建议收藏」

    13款国内外知名PHP集成环境的优缺点分析,PHP集成环境推荐、PHP绿色集成环境推荐「建议收藏」在本地测试网站,有个集成环境直接测试还是蛮方便的,下面向各位推荐国内和国外各种牛逼的php集成环境 排名不分先后! Xampp集成环境下载解压就能使用了,还支持苹果系统,溜的飞起。英文界面,用着B格也提高了不少。优点:支持的系统多啊,软件使用简单,可视化界面缺点:没有集成VC运行库,遗憾  然后就是老牌的apm

  • cas算法是什么_对算法的认识

    cas算法是什么_对算法的认识应用原子操作类,例如AtomicInteger,AtomicBoolean …适用于并发量较小,多cpu情况下;Java中有许多线程安全类,比如线程安全的集合类。从Java5开始,在java.util.concurrent包下提供了大量支持高效并发访问的集合接口和实现类。如:ConcurrentMap、ConcurrentLinkedQueue等线程安全集合。引入问题那么问题来了,这些线程安全类的底层是怎么保证线程安全的,你可能会想到是不是使用同步代码锁synchronized?引入概念这些线

  • 从零开始学android编程之网格布局管理器(2-1)

    从零开始学android编程之网格布局管理器(2-1)网格布局管理器用GridLayout类来表示。在《从零开始学android编程之表格布局管理器》中提到的TableLayout一般产生的表格外形是标准的方框,而GridLayout类产生的网格可以是不标准的。1设置网格的行数和列数在《从零开始学android编程之线性布局管理器》中提到的activity_linear.xml文件中使用表格布局管理器GridLayout,代码如下Lin

  • word2vec训练中文词向量

    word2vec训练中文词向量词向量作为文本的基本结构——词的模型。良好的词向量可以达到语义相近的词在词向量空间里聚集在一起,这对后续的文本分类,文本聚类等等操作提供了便利,这里简单介绍词向量的训练,主要是记录学习模型和词向量的保存及一些函数用法。一、搜狐新闻1.中文语料库准备本文采用的是搜狗实验室的搜狗新闻语料库,数据链接http://www.sogou.com/labs/resource/cs.php下载下来的…

  • 虚拟机ifconfig或ip addr不显示ip地址「建议收藏」

    虚拟机ifconfig或ip addr不显示ip地址「建议收藏」虚拟机ifconfig或ipaddr不显示ip地址报错图片:一直查不到ip地址,有重新启动很多次解决方法(1)命令查看配置文件:vi/etc/sysconfig/network-scripts/ifcfg-ens33ens33注意看这个修改的文件后缀把ONBOOT的状态no改为yes然后重启,应该就没问题了。(2):还有一种可能是因为虚拟网卡没有正常连接,解决方法是开启虚拟网卡的服务:打开任务管理器,选择服务标签,为了保险,开启所有的和vmware有关的服务检

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号