实验二+动态规划

实验代码： 实验1

package com;

public class Aoo {

public static int LongestIncreasingSubsequence(int x[],int c[],int[]line){

int n = x.length;

int path[] = new int[n]; for(int i=0;ic[0] = 1;

for(int i=1;ifor(int j=0;jif(x[i]>=x[j] && c[j]+1>c[i]){ c[i] = c[j] +1; path[i] = j; } } }

int max = 0; int end = -1;

for(int i=0;imax){ max = c[i]; end = i; } }

int i = 1;

line[0] = x[end];

while(path[end]!= end){

line[i++] = x[path[end]]; end = path[end]; }

return max; }

public static void main(String[] args) {

int[] x = new int[]{1,5,8,10,11,3,15,9,16}; int[] c = new int[x.length]; int[] line = new int[x.length];

}

}

int max = Aoo.LongestIncreasingSubsequence(x, c, line); System.out.println(\"最长单调递增子序列的长度为：\"+max); for(int i=max-1;i>=0;i--){

System.out.print(line[i]+\); }

实验2

package com;

public class Knapsack {

public static int[][] knapsack(int[]w,int[]v,int c){ int i,j,n=w.length;

int[][] m = new int[n+1][c+1]; for( i=1;ifor( j=0;jfor(i=1;i<=n;i++)

for(j=1;j<=c;j++){

m[i][j] = m[i-1][j]; if(w[i-1]<=j)

if(v[i-1]+m[i-1][j-w[i-1]]>m[i-1][j]) m[i][j] = v[i-1]+m[i-1][j-w[i-1]]; }

return m; }

public static int[] buildSolution(int[][]m,int[]w,int c){ int j=c,n=w.length; int[] x = new int[n]; for(int i = n;i>=1;i--) if(m[i][j]==m[i-1][j]) x[i-1]=0; else{

x[i-1]=1; }

return x; }

public static void main(String[] args) { int[]w={3,4,5,7}; int v[]={4,5,7,10}; int[] x;

}

}

int[][]m;

m = Knapsack.knapsack(w, v,9);

x = Knapsack.buildSolution(m, w, 9); for(int i =0;i<4;i++){

System.out.print(x[i]+\" \"); System.out.println(); }

一、实验目的

（1）理解动态规划算法设计思想和方法； （2）培养学生的动手能力。

二、实验工具

（1）JDK1.8

（2）Eclipse IDE for Java EE Developers

三、实验题：

1、设计一个

时间的算法，找出由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向量

使得

因此，二维0-1背包问题也是一个特殊的整数规划问题。

而且

达到最大。

容易证明该问题具有最有子结构特征。 设所给二维0-1背包问题的子问题

的最优值为

，即

是背包容量为j，容积为k，可选物品为i,i+1，…，n时二维

的

0-1背包问题的最优值。由于二维0-1背包问题的最有子结构性质，可以建立计算递归式如下：

按此递归式计算的

为最优值，算法所需的计算时间为

。

一维0-1背包问题代码如下：

四、实验报告要求

（1）完成实验内容；

（2）记录实验过程存在的问题，书写实验报告。

五、实验思考题