背包问题-动态规划java实现代码

背包问题-动态规划java实现代码背包问题-动态规划背包问题是如今面试流行的面试题之一,我们可用动态规划解题

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

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

背包问题-动态规划


一、动态规划的原理

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。
动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。举例:线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;背包问题:01背包问题,完全背包问题,多重背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

二、分析与代码实现

1、分析

题目:在某个深夜里,一个小偷背着一个总共只能装16v体积的背包进入一家商店偷东西。假如店里有手机一部,价格为2000元,体积为1v;薯片一包,价格为5元,体积为5v;翡翠一块,价格为100000元,体积为10v;一套四大名著,价格30元,体积为6v;电脑一台,价格为6000元,体积为10v。怎么样能够让背包装的下,并且又能使拿到的东西总价格最多?

这种情况下,一共5件东西。小偷偷东西的事件只有两种:拿,不拿。
当他拿的时候,背包体积变小,物件数量减1;当他不拿的时候,背包体积不变,物件数量减1(因为小偷选择不拿这件东西的时候不会返回继续拿,所以他失去了这件东西选择的机会)。

物件数量为i,背包容纳量为v。

1.不拿 b(i-1,v)
2.拿 b(i-1,v-该物品的体积)
两者取最大值

核心代码:

b[i][j]=Math.max(b[i-1][j],b[i-1][j-v]+p);

2、代码分析

public class _背包问题 { 
   

    //物品体积
    private static int[] volume={ 
   1,5,10,6,10};
    //物品价格
    private static int[] price={ 
   2000,5,100000,30,6000};
    //背包容量
    private static int maxVolumen=16;
    //物品数量
    private static int count=5;

    public static int solution(int maxVolumen,int count,int[] volume,int[] price){ 
   
        int[][] b=new int[count+1][maxVolumen+1];
        for (int i=1;i<=count;i++){ 
   
            //拿到物品的价格
            int p=price[i-1]; 
            //拿到物品的体积
            int v=volume[i-1];  
            for (int j=1;j<=maxVolumen;j++){ 
   
                //如果物品的体积大于背包容量时,选择不拿。
                if (j<v){ 
   
                    b[i][j]=b[i-1][j];
                    continue;
                }
                b[i][j]=Math.max(b[i-1][j],b[i-1][j-v]+p);
            }
        }
        return b[count][maxVolumen];
    }

    public static void main(String[] args) { 
   
        System.out.println(solution(16,5,volume,price));
    }
}

本人初次写博客,在b站学子烁老师视频而总结的,如有不好之处,请多多指教。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 【机器学习中的数学】多项式分布及其共轭分布

    【机器学习中的数学】多项式分布及其共轭分布多项变量(MultinomialVariables)二元变量是用来描述只有两种可能值的量,而当我们遇到一种离散变量,其可以有K种可能的状态。我们可以使用一个K维的向量x表示,其中只有一维xk为1,其余为0。对应于xk=1的参数为μk,表示xk发生时的概率。其分布可以看做是伯努利分布的一般化。现在我们考虑N个独立的观测D={x1,…,xN},得到其似然函数。如图:

    2022年10月11日
  • Srvctl命令详解(10g)「建议收藏」

    Srvctl命令详解(10g)「建议收藏」Srvctl命令 Srvctl命令式RAC维护中最常用的命令也是最复杂的命令。这个工具用来维护一下几种资源:Database,Instance,ASM,Service,Listener和NodeApplication,nodeApplication又包括GSD,ONS,VIP。 Srvctl命令的用法: [root@felix2bin]#./srvctl-help…

  • table css样式_html table居中

    table css样式_html table居中12345html简单的table样式67/*gridtable*/8table.gridtable{9font-family:verdana,arial,sans-serif;10font-size:11px;11color:#333333;12border-width:1px;13border-color:#666666;14bor…

  • 一篇文章带你搞懂DEX文件的结构[通俗易懂]

    一篇文章带你搞懂DEX文件的结构[通俗易懂]*本篇文章已授权微信公众号guolin_blog(郭霖)独家发布本文地址:一篇文章带你搞懂DEX文件的结构DEX文件就是AndroidDalvik虚拟机运行的程序,关于DEX文件的结构的重要性我就不多说了。下面,开练!建议:不要只看,跟着我做。看再多遍不如自己亲自实践一遍来的可靠,别问我为什么知道。泪崩ing…..首先,我们需要自己构造一个dex文件,因为自己构造的比…

  • C#的WinForm窗体程序中如何设置TextBox为密码文本框

    C#的WinForm窗体程序中如何设置TextBox为密码文本框C#的WinForm窗体程序中如何设置TextBox为密码文本框-2019-08-0323:59在C#的WinForm窗体程序开发过程中,TextBox是常用的文本框控件,默认的TextBox

  • UE4投影矩阵[通俗易懂]

    UE4投影矩阵[通俗易懂]UE4投影矩阵正交投影classFOrthoMatrix :publicFMatrix{public: /** *Constructor * *@paramWidthviewspacewidth *@paramHeightviewspaceheight *@paramZScalescaleintheZaxis *@paramZOffsetoffsetintheZaxis */ FOrthoMatrix(flo

发表回复

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

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