精华内容
下载资源
问答
  • 上图表达的是一个人在工厂上班的任务计划,横坐标代表时间,灰色区域的黑色数字代表任务的编号,红色数字代表完成任务所得到的报酬,并且这个人在同一时间内只能完成一个任务,这个在这一天工作中所获得的最大报酬...

    上图表达的是一个人在工厂上班的任务计划,横坐标代表时间,灰色区域的黑色数字代表任务的编号,红色数字代表完成任务所得到的报酬,并且这个人在同一时间内只能完成一个任务,求这个在这一天工作中所获得的最大报酬。

    下面是由题意列出的递归方程:

    opt(i)=v(i)+opt(prev(i)) 选择当前的任务

    opt(i) = opt(i-1) 不选择当前的任务

    上面方程中的opt(i)代表考虑到任务i时所获得的最大报酬,v(i)代表当前任务i所对应的报酬,prev(i)代表当前任务i前面还可以做哪个任务。由图得到了v(i)和prev(i)所对应的数组int[] prev = new int[] {0,0,0,1,0,2,3,5};和

    int[] v = new int[] {5,1,8,4,6,3,2,4};所以最后得到了这个递归方程所对应的java代码:

    public class ChoiceOrNot {
    	//存储在选择第i个任务时,它前面可以做的任务编号,0表示无任务可做
    	static int[] prev = new int[] {0,0,0,1,0,2,3,5};
    	//存储每个任务所对应的价值
    	static int[] v = new int[] {5,1,8,4,6,3,2,4};
    	
    	//比较两个整数的大小,并返回较大的整数
    	public static int max(int a,int b) {
    		if(a>=b) 
    			return a;
    		else
    			return b;
    				
    	}
    	
    	//求做任务可以得到的最大价值(递归法)
    	public static int rec_opt(int i) {
    		if(i<=0)
    			return 0;
    		if(i==1) 
    			return v[i-1];
    		int choice = v[i-1] + rec_opt(prev[i-1]);
    		int notChoice = rec_opt(i-1);
    		return max(notChoice,choice);
    	}
    	
    	//求做任务可以得到的最大价值(动态规划法)
    	public static int dp_opt() {
    		int[] opt = new int[v.length+1];
    		opt[0] = 0;
    		opt[1] = v[0];
    		for(int i=1;i<opt.length;i++) {
    			int choice = v[i-1]+opt[prev[i-1]];
    			int notChoice = opt[i-1];
    			opt[i] = max(choice,notChoice);
    		}
    		return opt[opt.length-1];
    	}
    	
    	public static void main(String[] args) {
    		int result1 = rec_opt(8);
    		int result2 = dp_opt();
    		System.out.println(result1);
    		System.out.println(result2);
    	}
    }

    运行结果为:



    展开全文
  • 01背包问题最大价值
        在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
       注意:在本题中,所有的体积值均为整数。01的意思是,每个物品都是一个整体,要么整个都要,要么都不要。
        1)最优子结构
        考虑所有物品的子集合,考虑第n个物品都有两种情况: 1. 包括在最优方案中  2. 不在最优方案中因此,能获得的最大价值,即为以下两个值中较大的那个
            1) 在剩下 n-1 个物品中(剩余 W 重量可用)的情况能得到的最大价值 (即排除了 第n个物品)
            2)  第n个物品的价值 加上 剩下   剩下的 n-1 个物品(剩余W- wn的重量)能得到的最大价值。(即包含了第n个物品)
        如果第n个物品的重量,超过了当前的剩余重量W,那么只能选情况1), 排除第n个物品。

        2) 重叠子问题*/

    具体实例及实现代码如下所示:

    /**
     * @Title: ZeroOneKnapSack.java
     * @Package dynamicprogramming
     * @Description: TODO
     * @author peidong
     * @date 2017-6-8 上午8:54:18
     * @version V1.0
     */
    package dynamicprogramming;
    
    /**
     * @ClassName: ZeroOneKnapSack
     * @Description: 0-1背包问题
     * @date 2017-6-8 上午8:54:18
     *
     */
    
    public class ZeroOneKnapSack {
    
        /**
         *
         * @Title: knapSackRecursion
         * @Description: 递归求解0-1 规划问题  , 返回前n个物品在容量为w,得到的最大价值
         * @param w 背包总重量
         * @param wt 物品重量数组
         * @param vt 物品价值数组
         * @param n 物品数量
         * @return
         * @return int
         * @throws
         */
        public static int knapSackRecursion(int w, int[] wt, int[] vt, int n){
            //边界条件判断
            if(n == 0 || w ==0)
                return 0;
            //d当前n个物品超重时
            if(wt[n-1] > w)
                return knapSackRecursion(w, wt, vt, n-1);
            else
                return Math.max(vt[n-1] + knapSackRecursion(w-wt[n-1], wt, vt, n-1), knapSackRecursion(w, wt, vt, n-1));
            //返回如下两种情况较大值(1)包含第n个物品(2)不包含第n个物品
        }
    
        public static int knapSack(int w, int[] wt, int[] vt, int n){
            //创建状态转移矩阵
            int[][] tc = new int[n+1][w+1] ;
    
            //构建状态转移矩阵
            for(int i = 0; i<= n; i++){
                for(int j = 0; j <= w; j++){
                    //边界条件
                    if(i == 0 || j == 0){
                        tc[i][j] = 0;
                    }else if(wt[i-1] <= j)
                        tc[i][j] = Math.max(vt[i-1] + tc[i-1][j-wt[i-1]], tc[i-1][j]);
                    else
                        tc[i][j] = tc[i-1][j];
                }
            }
            return tc[n][w];
        }
        /**
         * @Title: main
         * @Description: TODO
         * @param args
         * @return void
         * @throws
         */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
    
            int[] vt = {1, 1, 2, 2, 3, 3, 4, 5};
            int[] wt = {8, 10, 13, 15, 20, 24, 28, 33};
            int w = 12;
            int n = vt.length;
    
            System.out.println("利用递归求解01背包问题最大价值为:" + knapSackRecursion(w, wt, vt, n));
            System.out.println("利用动态规划求解01背包问题最大价值为:" + knapSack(w, wt, vt, n));
        }
    
    }
    


    展开全文
  • 已知一个长宽高分别为m,n,h的立方体,且利比阿尼每一立方体都有一定的价值,要求求得一个子立方体,使得子立方体内部的每个小立方体的权值之和最大,  思想就是,将三维的子立方体转换成一维的处理,用rec[i,j,k]...

         已知一个长宽高分别为m,n,h的立方体,且利比阿尼每一立方体都有一定的价值,要求求得一个子立方体,使得子立方体内部的每个小立方体的权值之和最大,

        思想就是,将三维的子立方体转换成一维的处理,用rec[i,j,k]表示z轴坐标为k的平面矩形(1,1,i,j)的数和,其中(1,1)表示子矩阵的左上角坐标,(i,j)表示子矩阵的右下角坐标,那么状态转移方程可以表示为

    则z轴坐标为z的水平面中左上角为(x1,y1)、右下角为(x2,y2)的矩阵的数和为rec[x2,y2,z] + rec[x1,y1,z] - rec[x2,y1,z] - rec[x1,y2,z]

    展开全文
  • 题干:现有电脑(价格2000尺寸3)、手机(价格3000尺寸2)、电视(价格1000尺寸4)、收音机(价格500尺寸1)各一件,你有一个背包,背包最大可装尺寸6,问能装的物品总价最高为多少? 拓展:如果是任意n多个物品,物品的...

    题干:现有电脑(价格2000尺寸3)、手机(价格3000尺寸2)、电视(价格1000尺寸4)、收音机(价格500尺寸1)各一件,你有一个背包,背包最大可装尺寸6,问能装的物品总价最高为多少?

    拓展:如果是任意n多个物品,物品的价格和尺寸分别为price_list[0]、price_list[1]、price_list[2]…price_list[n-1]和size_list[0]、size_list[1]、size_list[2]…size_list[n-1],背包空间尺寸大小为space,求最大可装价值?
    def test(price_list=[], size_list=[], space=0):
        """任意多商品的价格和尺寸以及背包大小传入,计算最大可装价值"""
        n=len(price_list)
        db=[[0 for i in range(space + 1)] for j in range(n + 1)]
        for i in range(1, n+1):
            for j in range(space + 1):
                if size_list[i-1] <= j:
                    db[i][j] = max(db[i - 1][j], db[i - 1][j - size_list[i-1]] + price_list[i-1])
                else:
                    db[i][j] = db[i - 1][j]
        return db[-1][-1]
    
    """电脑、手机、电视、收音机"""
    """价格表"""
    price_list = [2000, 3000, 1000, 500]
    
    """尺寸表"""
    size_list = [3, 2, 4, 1]
    
    """背包空间"""
    space = 6
    
    """背包可以装的最大价值为"""
    print(test(price_list, size_list, space))
    
    展开全文
  • 礼物的最大价值题目描述思路空间复杂度优化:代码复杂度分析: 题目描述 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右...
  • 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 动态规划背包问题的优化解题思路以及方法
  • 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 i(物品编号) ...
  • 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的...
  • 一个m*n的矩阵,只能向右走或是向下走,矩阵每一个元素代表一个财富值,要求打印出从左上角到右下角走的财富最大总值。 如输入m=4 ,n=5, 输入矩阵value= { 0 0 7 0 0 ,  0 0 0 5 0,  2 0 4 0 0,  0 0 0 3 0}, ...
  • 利用动态规划求迷宫的最优值问题

    千次阅读 2009-09-28 11:30:00
    【问题】7月5号的那道题的动态规划解法和如下这道的动态规划解法大体一致 从【0,0】出发走到底线处即停止,矩阵中每个元素的值为该处可以获得的价值,问到达底线时能获得的最大值。【动态规划】 规划一个二维矩阵...
  • 动态规划

    千次阅读 多人点赞 2017-08-30 16:15:42
    动态规划前几天被阿里校招笔试一道装箱问题的编程题吓懵逼了,遂决定好好看看动态规划的东西,结合在牛客网上的课程,总结一下基础动态规划的知识。动态规划的关键点在于解决冗余和记忆化搜索。当遇到一道需要暴力...
  • 动态规划解决币值最大化问题

    千次阅读 2019-05-15 22:40:03
    币值最大化 问题描述 给定一排n个硬币,其面值均为整数c1, c2, …, cn, 这些整数并不一定两两不同。问如何选择硬币,使得在其原始位置互不相邻的条件下,所选硬币的总金额最大。 解题思路 上述最大可选金额用f(n...
  • 问题:  某厂根据计划安排,拟将n台相同的设备...动态规划法: 算法思想:  将m个车间划分为前m-1个和第m个,每次给第m个车间分配的时候都是建立在前m-1的最优策略的基础上(总利润最大),再进行最优分配。这样
  • #include using namespace std;//动态规划:0-1背包问题//bestValue[i][j]=max ( bestValue[i+1][j-w[i]]+v[i] ,bestValue[i+1][j] ) w[i][i][j]=bestValue[i+1][j] w[i]>jclass Knapsac
  • Java 动态规划

    万次阅读 多人点赞 2019-06-23 16:16:43
    Java中的动态规划 介绍 动态规划典型的被用于优化递归算法,因为它们倾向于以指数的方式进行扩展。动态规划主要思想是将复杂问题(带有许多递归调用)分解为更小的子问题,然后将它们保存到内存中,这样我们就不必在...
  • 动态规划算法

    千次阅读 2016-12-26 20:49:05
    1. 动态规划算法动态规划:通过把原问题分解为相对简单的子问题来求解复杂问题。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 算法总体思想 动态规划算法与分治法类似,其基本思想也是将待求解问题...
  • 初识动态规划

    千次阅读 热门讨论 2021-03-13 20:22:17
    实战演练4.1机器人不同路径4.2 礼物的最大价值4.3硬币4.4三步问题 1.什么情况下使用动态规划 一个问题可以分解为子问题,且子问题之间具有联系互相影响,同时还需要有最优的子结构 注意的是这是一个必要不充分条件...
  • 动态规划(Dynamicprogramming) 是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题...
  • 简单动态规划

    千次阅读 2021-03-11 23:26:41
    简单动态规划 简单背包问题 : 假设你要去野营。你有一个容量为6磅的背包,需要决定该携带下面的哪些东西。其中 每样东西都有相应的价值价值越大意味着越重要: 1 水(重3磅,价值10); 2 书(重1磅,价值3); 3...
  • 翻译你是一个专业强盗,并计划沿街去盗窃每一个...给定一系列非负整数代表每个房子的金钱,出再不惊动警察的情况下能盗窃到的最大值。原文You are a professional robber planning to rob houses along a street. Ea
  • 虽然我们已经用动态规划方法解决了钢条切割和矩阵链乘法两个问题,但你可能还是弄不清应该在何时使用动态规划。我们关注适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。我们还会...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 42,371
精华内容 16,948
关键字:

动态规划求最大价值