实验二 动态规划

1、实验二动态规划姓名：陈国华班级：软1241学号：121842295一、实验目的（1）理解动态规划算法设计思想和方法；（2）培养学生的动手能力。二、实验工具（1）JDK1.8（2）Eclipse IDE for Java EE Developers三、实验题：1、设计一个时间的算法，找出由n个数组成的序列的最长单调递增子序列。2、给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值是vi，背包的容量 为C，容积为D。问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？（在选 择装入背包中的物品时，对于每一种物品i只有两种选择，即装入背包或不装入背包。不能 将物品1装入背包多次，

2、也不能只装入物品i的一部分）。三、实验提示：1、对于X0-n中的每一个元素xi，求出以它结尾的X0i的LIS，保存在数组lis中， 然后找出lis中最大的元素，即X0n的LIS。假设求X0i的LIS，即求lisi,那么在X0i-1寻找x0，x1，xi-1中所有小于xi 的元素xj（0 = j = i-1 ），对于每一个xj，都有一个以它结尾的序列X0j的最长单调递增 子序列，其长度自然为lisj，然后从这些lisj找出最大的元素，那么lisi就等于这个lisj 加1,这就是X0i的LIS。而如果X0i-1中没有小于xi的元素，那么lisi等于1。该解法的时间复杂度为O（n2）。算法：publi

3、c class ssss (public static int LongestIncreasingSubsequence(int x,int c, int line)( int n=x.length;int path=new intn;for(int i=0;in;+i)( pathi=i; c0=1;for(int i=1;in;+i)( ci=1;for(int j=0;j=xj& cj+1ci) ci=cj+1; pathi=j;int max =0;int end=-1;for(int i=0;imax) max=ci; end=i;int i=1;line0=xend;while(p

4、athend!=end) linei+=xpathend; end=pathend; return max; public static void main(String args)int x=new int 口1,3,5,4,6,9,7,8,11;int c=new intx.length;int line=new intx.length;int max=ssss.LongestIncreasingSubsequence(x, c, line);System.out .println(最长单调递增子序列的长度为：+max); for(int i=max-1;i=0;-i)System.out

5、 .print(linei+,);结果：最杖卑调递增于序列阿杖度为：72、该问题是二绳）-1背包问题。问题的形式化描述是：给定，要求找出n元0-1向量使得 而且达到最大。因此，二维0-1背包问题也是一个特殊的整数规划问题。容易证明该问题具有最有子结构特征。设所给二维0-1背包问题的子问题的最优值为，即是背包容量为j,容积为k，可选物品为1,2，i时二维0-1背包问题的最优值。由于二维0-1背包问题的最有子结构性质，可以建立计算的递归式如下：按此递归式计算的为最优值，算法所需的计算时间为。一维0-1背包问题代码如下：public class ssss ( public static int Kn

6、apsack(int w, int v, int c) ( int i,j,n = w.length;int m = new intn+1c+1; for(i=1;in+1;i+) mi0 = 0; for(j=0;jc+1;j+) m0j = 0; for(i=1;i=n;i+) for(j=1;j=c;j+)( mij = mi-1j; if(wi-1 mi-1j) mij = vi-1+mi-1j-wi-1;return m; public static int buildSolution(int m, int w, int c) ( int i,j = c,n = w.length;int x = new intn;for(i=n;i=1;i-)if (mij = mi-1j) xi-1 = 0;else(xi-1 =1;j -= wi-1;return x;public static void main(String args)( int w = 2,3,4,5,v = 3,4,5,8; int m;int x;m=ssss.Knapsack(w,