Java使用动态规划算法思想解决背包问题

目录
  • 动态规划算法
    • 动态规划算法的思想
    • 最优性原理
    • 动态规划算法的三大特点
    • 动态规划算法中的0/1背包问题
    • 动态规划算法的优点
  • 小结

动态规划算法

动态规划算法的思想

动态规划算法处理的对象是多阶段复杂决策问题,动态规划算法和分治算法类似,其基本思想也是将待求解问题分解成若干个子问题(阶段),然后分别求解各个子问题(阶段),最后将子问题的解组合起来得到原问题的解,但是与分治算法不同的是,子问题往往不是相互独立的,而是相互联系又相互区别的

动态规划算法问题求解的目标是获取导致问题最优解的最优决策序列(最优策略)。对于一个决策序列,可以用一个数值函数(目标函数)衡量这个决策的优劣。

最优性原理

动态规划算法的最优性原理:一个最优决策序列具有这样的性质,不论初始状态和第一步决策如何,对前面的决策所形成的状态而言,其余的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。

最优性原理体现为问题的最优子结构特性,对于一个问题,如果能从较小规模的子问题的最优解求得较大规模同类子问题的最优解,最终得到给定问题的最优解,也就是问题的最优解中所包含的子问题的最优解,这种性质被称为最优子结构性质。最优子结构特性使得在从较小问题的解构造较大问题的解时,只需考虑子问题的最优解,然后以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解,它保证了原问题的最优解可以通过求解子问题的最优解来获得,最优子结构的特性是动态规划算法求解问题的必要条件。

动态规划算法的三大特点

  • 如果求解的问题满足最优性原理,则说明用动态规划算法有可能解决该问题,在分析问题的最优子结构时,所使用的方法具有普遍性。要注意一个问题可以有多种方式刻画它的最优子结构,有些表示方法的求解速度更快(空间占用少,问题的维度低)。
  • 递归定义最优解决方案。动态规划的每一步决策都依赖于子问题的解,动态规划算法求解最优化问题的步骤为:找出最优解的结构,具体来说就是看这个问题是否满足最优子结构特性;其次递归定义一个最优解的值,即构造原问题和子问题之间的递归方程,原问题的最优解可以通过子问题的最优解获得。
  • 以自底向上的方式计算出最优解的值(最优解的目标函数的值)。对子问题的分解是基于原问题的分解的基础之上进行的,而且这些子问题的分解过程是相互独立的。在对原问题分解的过程中,会出现大量的共享重叠子问题,为了避免对大量重叠子问题的重复计算,一般动态规划算法从自底向上开始计算,对每一个问题只解一次,并且保存求解子问题的最优值,当再需要求解这个子问题的时候,可以用常数时间查看一下结果,而不是再递归的去求解每一个问题的解,因此提高了动态规划算法的效率。

动态规划算法中的0/1背包问题

0/1背包问题的规则是不允许该物品进行拆分,即只有把物品放入和不放入两个基本状态,要使用动态规划算法求解决如何放物品才可以是背包中的物品的总价值达到最高。

示例

有一个载重为10的背包,现有4类物品,每类物品的重量分别为(w0,w1,w2,w3)=(2,3,4,7),它们的价值分别为(p0,p1,p2,p3)=(1,3,5,9)。试问如何装载能够使背包容纳物品的价值最大。

package 算法设计与分析;
 import java.util.Arrays;
 import java.util.Scanner;
 //m表示的是背包的容量,a表示有多少种类的物品,数组w用与存放每类物品的重量,数组val用于存放每类物品的价值
 public class my {
     public static void main(String[] args) {
         Scanner scanner = new Scanner(System.in);
         System.out.print("请输入背包的容量:");
         int m = scanner.nextInt();
         Scanner inScanner = new Scanner(System.in);
         System.out.print("请输入物品的个数:");
         int a = inScanner.nextInt();
         int[] w = new int[a + 1];
         System.out.print("请输入物品的重量:" + " ");
         for (int i = 1; i <= a; i++) {
             w[i] = inScanner.nextInt();
         }
         int[] val = new int[a+ 1];
         System.out.print("请输入物品的价值:" + " ");
         for (int i = 1; i <= a; i++) {
             val[i] = inScanner.nextInt();
         }
         int n = val.length;
         int[][] path = new int[n +1][m+1 ];
         //创建二维数组
         //v[i][j]:表示在前i个物品中能够装入容量为j的背包中的最大价值
         int[][] v = new int[n +1][m + 1];
         //初始化第一行和第一列
         for (int i = 0; i < v.length; i++) {//v.length:获取二维数组的行数
             v[i][0] = 0;//将第一列设置为0
         }
         for (int i = 0; i < v[0].length; i++) {//v[0].length:获取二维数组的列数
             v[0][i] = 0;//将第一行设置为0
         }
         for (int i = 1; i < v.length; i++) {//int i = 1 不处理第一行
             for (int j = 1; j < v[0].length; j++) {//int j = 1 不处理第一列
                 if (w[i - 1] > j) {
                     v[i][j] = v[i - 1][j];
                 } else {
                     if (v[i - 1][j] < (val[i - 1] + v[i - 1][j - w[i - 1]])) {
                         v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                         //把当前情况记录到path
                         path[i][j] = 1;
                     } else {
                         v[i][j] = v[i - 1][j];
                     }
                 }
             }
         }
         //输出二维数组:
         for (int[] ints : v) {
             System.out.println(Arrays.toString(ints));
         }
         //输出最后我们是放入的那些商品
         int i = path.length - 1;//行的最大下标
         int j = path[0].length - 1;//列的最大下标
         while (i > 0 && j > 0) {//从path的最后开始找
             if (path[i][j] == 1) {
                 System.out.printf("第%d个商品放入背包\n", i-1);
                 j -= w[i - 1];
             }
             i--;
         }
     }
 }

输入一个背包容量为10,里面有4类物品,物品的重量分别为2,3,4,7,物品的价值分别为1,3,5,9

结果

动态规划算法的优点

若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

小结

以上就是针对动态规划算法的详细分析,利用动态规划算法可以避免重复计算多次子问题,提高效率,使计算机的性能更好!

到此这篇关于Java使用动态规划算法思想解决背包问题的文章就介绍到这了,更多相关Java背包问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 背包问题-动态规划java实现的分析与代码

    一.动态规划的原理 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划.1957年

  • Java实现动态规划背包问题

    目录 前言 一.原理 1.1 最优子结构性质 1.2 递归关系 二.算法描述 2.1 算法描述 2.2 图解 2.3 构造最优解 三. 0 − 1 0-1 0−1 背包问题相关题目 3.1 题目 3.2 源程序(Java求解 0 − 1 0-1 0−1背包问题) 3.3 运行结果 总结 前言 给定 n n n 种物品和一个背包.物品 i i i 的重量是 w i wi wi,其价值为 v i vi vi,背包的容量为 c c c.问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 一.

  • java背包问题动态规划算法分析

    背包问题 [题目描述] 一个旅行者有一个最多能装 MM 公斤的背包,现在有 nn 件物品,它们的重量分别是W1,W2,-,WnW1,W2,-,Wn,它们的价值分别为C1,C2,-,CnC1,C2,-,Cn,求旅行者能获得最大总价值. [输入] 第一行:两个整数,MM(背包容量,M<=200M<=200)和NN(物品数量,N<=30N<=30): 第2-N+12-N+1行:每行二个整数Wi,CiWi,Ci,表示每个物品的重量和价值. [输出] 仅一行,一个数,表示最大总价值. [输入

  • Java使用动态规划算法思想解决背包问题

    目录 动态规划算法 动态规划算法的思想 最优性原理 动态规划算法的三大特点 动态规划算法中的0/1背包问题 动态规划算法的优点 小结 动态规划算法 动态规划算法的思想 动态规划算法处理的对象是多阶段复杂决策问题,动态规划算法和分治算法类似,其基本思想也是将待求解问题分解成若干个子问题(阶段),然后分别求解各个子问题(阶段),最后将子问题的解组合起来得到原问题的解,但是与分治算法不同的是,子问题往往不是相互独立的,而是相互联系又相互区别的 动态规划算法问题求解的目标是获取导致问题最优解的最优决策序

  • C++回溯与分支限界算法分别解决背包问题详解

    目录 算法思想 回溯代码 分支限界代码 算法思想 分支限界法与回溯法的求解目标不同. 回溯法的求解目标是找出解空间中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解. 由于求解目标不同,导致分支限界法与回溯法对解空间的搜索方式也不相同. 回溯法以深度优先的方式搜索解空间,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间. 回溯法对解空间做深度优先搜索时,有递归回溯和迭代回溯(非

  • Python基于动态规划算法解决01背包问题实例

    本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re

  • Java 数据结构与算法系列精讲之背包问题

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 动态规划 动态规划 (Dynamic Programming) 的核心思想是把大问题划分为小问题进行解决. 先求解子问题, 然后从这些子问题的解得到原问题的解. 动态规划的优点: 可以帮助我们解决多阶段问题, 化繁为简 动态规划的缺点: 没有统一的处理方法, 具体问题具体分析 当变量的维数增大时, 计算和存储会急剧增大 背包问题 背包问题 (Knapsack Problem) 指有 N 件物品和一个容量为 V 的背包

  • java动态规划算法——硬币找零问题实例分析

    本文实例讲述了java动态规划算法--硬币找零问题.分享给大家供大家参考,具体如下: 问题描述 现在有3种硬币分别为:1元,5元,10元,现在给你63元,让你全部换成硬币,求出最小硬币数量,也就是说,怎么用最少的硬币数凑成63元. 分析问题 解决这个问题,我们可以将这个大问题分成若干个小问题,自下而上解决问题. 1元对应的最小硬币数是1 2元对应的最小硬币数是2 3元对应的最小硬币数是3 4元对应的最小硬币数是4 -- 63元对应的最小硬币数是XXX 假设我们将前边计算出的金额对应的最小硬币数像

  • Python动态规划实现虚拟机部署的算法思想

    声明 本文章为个人拙见,仅仅提供参考,不一定正确,各位大佬可以发表自己的意见. 题目描述 考虑到在虚拟机部署中资源提供商通常希望自己的收益最大化,现假设有一台宿主机,共有x个cpu和y GB的内存,用户可以采取自己报价的方式向资源提供商申请使用虚拟机资源,譬如说付w元申请a个cpu和b GB内存的一台虚拟机.请你设计一个算法,让资源提供商可以合理地安排虚拟机,使得自己的收益最大化. 输入: n x y 2 4 200 4 2 150 - 说明,n表示共有n条用户报价申请,宿主机共有x个cpu和y

  • Python算法思想集结深入理解动态规划

    目录 1. 概述 什么是重叠子问题 动态规划与分治算法的区别 什么最优子结构 2. 流程 2.1 是否存在子问题 2.2 是否存在重叠子问题 怎么解决重叠子问题 2.3 状态转移 3.总结 1. 概述 动态规划算法应用非常之广泛. 对于算法学习者而言,不跨过动态规划这道门,不算真正了解算法. 初接触动态规划者,理解其思想精髓会存在一定的难度,本文将通过一个案例,抽丝剥茧般和大家聊聊动态规划. 动态规划算法有 3 个重要的概念: 重叠子问题. 最优子结构. 状态转移. 只有吃透这 3 个概念,才叫

  • 深入解析堆排序的算法思想及Java代码的实现演示

    一.基础知识 我们通常所说的堆是指二叉堆,二叉堆又称完全二叉树或者叫近似完全二叉树.二叉堆又分为最大堆和最小堆. 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素.数组可以根据索引直接获取元素,时间复杂度为O(1),也就是常量,因此对于取值效率极高. 最大堆的特性如下: 父结点的键值总是大于或者等于任何一个子节点的键值 每个结点的左子树和右子树都是一个最大堆 最小堆的特性如下: 父结点的键值总是小于或者等于任何一个

  • Java矩阵连乘问题(动态规划)算法实例分析

    本文实例讲述了Java矩阵连乘问题(动态规划)算法.分享给大家供大家参考,具体如下: 问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1.确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数. 问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序.这种计算次序可以用加括号的方式来确定.若一个矩阵连乘积的计算次序完全确

随机推荐