实验二动态规划

实验二动态规划一、实验目的（1）理解动态规划算法设计思想和方法；（2）培养学生的动手能力。二、实验工具（1）JDK1.8（2）EclipseIDEforJavaEEDevelopers三、实验题：1、设计一个O(𝑛2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。2、给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值是vi，背包的容量为C，容积为D。问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？（在选择装入背包中的物品时，对于每一种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分）。三、实验提示：1、对于X[0···n]中的每一个元素xi，求出以它结尾的X[0···i]的LIS，保存在数组lis中，然后找出lis中最大的元素，即X[0···n]的LIS。假设求X[0···i]的LIS，即求lis[i],那么在X[0···i-1]寻找x0，x1，···，xi-1中所有小于xi的元素xj（0=j=i-1),对于每一个xj，都有一个以它结尾的序列X[0···j]的最长单调递增子序列，其长度自然为lis[j]，然后从这些lis[j]找出最大的元素，那么lis[i]就等于这个lis[j]加1，这就是X[0···i]的LIS。而如果X[0···i-1]中没有小于xi的元素，那么lis[i]等于1。由此可以得到递归方程：{()该解法的时间复杂度为O（n2）。2、该问题是二维0-1背包问题。问题的形式化描述是：给定𝑛，要求找出n元0-1向量{2}{}𝑛使得∑∑而且∑达到最大。因此，二维0-1背包问题也是一个特殊的整数规划问题。∑{∑∑{}𝑛容易证明该问题具有最有子结构特征。设所给二维0-1背包问题的子问题∑{∑∑{}的最优值为()，即()是背包容量为j，容积为k，可选物品为1,2，…，i时二维0-1背包问题的最优值。由于二维0-1背包问题的最有子结构性质，可以建立计算()的递归式如下：(){{()()}𝑛()(){𝑛按此递归式计算的()为最优值，算法所需的计算时间为O()。一维0-1背包问题代码如下：四、实验报告要求（1）独立完成实验内容；（2）记录实验过程存在的问题，书写实验报告。五、实验思考题