澳门新葡亰网址下载线性动态规划

by admin on 2020年1月22日

public class Swap {

一、编写一个简单程序,要求数组长度为5,分别赋值10,20,30,40,50,在控制台输出该数组的值。

线性动态规划

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub

package
com.test;

一、定义

  //交换法
  
  int[] score = new int[100];
  //初始化数组
  for (int i = 0; i <= score.length – 1; i++) {
   score[i] = (int)(Math.random() * 100);
  }

public
class t01 {

   
线性动态规划是指目标函数为特定变量的线性函数,约束是这些变量的线性不等式或等式,目的是求目标函数的最大值或最小值。

  
  int temp ;//中间变量
  int i ;
  int j ;
  for (i = 0; i < score.length – 1; i++) {
   int min = i;//假设最小值
   
   //找最小值
   for (j = i + 1; j <= score.length – 1; j++) {
    if (score[j] < min) {
     min = j;
    }
   }
   //交换最小值的位置
   if (min != i) {
    j–;
    temp = score[i];
    score[i] = score[j];
    score[j] = temp ;
   }
  }
  
  System.out.println(“排序后的数组:”);
  for (int k = 0; k <= score.length – 1; k++) {
   if (k % 10 == 0) {
    System.out.println();
   }
   System.out.print(score[k]+”t”);
  }
  
 }
 

public static void main(String[] args) {
//
静态初始化
int
i[] = new int[] { 10, 20, 30, 40, 50 };

二、典型例题

}

//
遍历数组
for
(int j = 0; j < 5; j++) {
System.out.print;
}
}

    1、最长上升序列问题

}

   
问题描述:设有序列B为B1,B2,B3……Bn,若存在下标i1<i2<i3<……in,且Bi1<Bi2<Bi3<……Bin,则序列B中有长度为n的上升序列Bi1,Bi2,Bi3,……Bin。求给定一序列中的最长上升序列长度及该序列。

效果图如下:

分析:

澳门新葡亰网址下载 1

    ①设f(i)是前i个数中以Bi结尾的最长上升序列的长度,

二、将一个字符数组的值(neusofteducation)考贝到另一个字符数组中。

则f(i)=max(f(j)+1),  (1<=j<i<=n,Bj<Bi),边界为f(1)=1;

package
com.test;

    ②设t(i)
是前i个数中所有最长上升序列的个数,初始t(i)=1,如果f(i)=n时,将t(i)累加,(  
1<=j<i<=n , Bi<Bj , f(i)=f(j)+1 )

public
class t02 {

例如

public static void main(String[] args) {
//
定义源字符数组
char[]
copy = { ‘n’, ‘e’, ‘u’, ‘s’, ‘o’, ‘f’, ‘t’, ‘e’, ‘d’, ‘u’, ‘c’, ‘a’,
‘t’, ‘i’, ‘o’, ‘n’ };

Bi

1

5

3

4

6

5

8

10

9

8

7

f(i)

1

2

2

3

4

4

5

6

6

5

5

T(i)

1

1

2

1

1

2

2

2

4

4

4

//
定义新字符数组
char[]
copyTo = new char[7];

 

/*

代码:

* System.arraycopy(Object src, int srcPos, Object dest, int destPos,
int length);

/*

* src:源数组; srcPos:源数组要复制的起始位置; dest:目的数组;
destPos:目的数组放置的起始位置;

*求最长上升子序列的元素的个数

* length:复制的长度

*/

*/
System.arraycopy(copy,
2, copyTo, 0, 7);

public class Long_list {

System.out.println(new
String;
}

   public static void main(String[] args) {

}

      int s[]={1,5,3,4,6,5,8,10,9};

效果图如下:

      int [] f=new int[s.length];

澳门新葡亰网址下载 2

      int [] t=new int[s.length];

三、给定一个有9个整数(1,6,2,3,9,4,5,7,8})的数组,先排序,然后输出排序后的数组的值。

      f[0]=1;

package
com.test;

      int maxLen=0;

public
class t03 {

      for (int i = 0; i < s.length; i++) {

public static void main(String[] args) {
//
定义数组
int[]
i = { 1, 6, 2, 3, 9, 4, 5, 7, 8 };

         for (int j = 0; j < i; j++) {

java.util.Arrays.sort;
// 排序

            if(s[i]>s[j]&&f[j]+1>f[i])

for
(int j = 0; j < i.length; j++) {
System.out.print(i[j]

                f[i]=f[j]+1;

  • ” “);
    }
    }

         }

}

         if(maxLen<f[i])

效果图如下:

            maxLen=f[i];

澳门新葡亰网址下载 3

      }

四、输出一个double型二维数组(长度分别为5、4,值自己设定)的值。

      System.out.println(f[f.length-1]);

package
com.test;

      Long_list l=new Long_list();

public
class t04 {

      //System.out.println(l.LIS_BSearch(s, t, s.length-1));

public static void main(String[] args) {
double[][]
dou = new double[5][4];

   }

for
(int i = 0; i < dou.length; i++) {
for
(int j = 0; j < dou[0].length; j++) {
System.out.println(dou[i][j]);
}
System.out.println();
}

}

}

 

}

//求最长上升子序列

效果图如下:

 

澳门新葡亰网址下载 4

public class LIS {

五、在一个有8个整数(18,25,7,36,13,2,89,63)的数组中找出其中最大的数及其下标。

 

package
com.test;

/*

public
class t05 {

 

public static void main(String[] args) {
int[]
arr = { 18, 25, 7, 36, 13, 2, 89, 63 };
int
max = arr[0];
int
maxIndex = 0;

 * 求一数列的最长上升子序列(元素都为非零元素)

for
(int i = 1; i < arr.length; i++) {
if
(max <= arr[i]) {
max =
arr[i];
maxIndex
= i;
}
}
System.out.println(“最大值为:”

 

  • max + “n最大值下标为:” + maxIndex);

 */

}

 

}

   public static void main(String[] args) {

效果图如下:

 

澳门新葡亰网址下载 5

      int []s ={1,2,9,4,6,7,4};

六、

 

有2个多维数组分别是
2 3 4 和 1 5 2 8

      //f数组来存储以其下标i(即s[i])结尾的最长上升序列元素的个数

4 6 8
5 9 10 -3

 

2 7 -5
-18

      int []f = new int[s.length];

按照如下方式进行运算。生成一个2行4列的数组。此数组的第1行1列是2*1+3*5+4*2

 

第1行2列是2*5+3*9+4*7
第2行1列是4*1+6*5+8*2 依次类推。

      //son数组来存储每个以s[i]结尾的最长上升子序列

package
com.test;

 

public
class t06 {
public
static void main(String[] args) {
int
a[][] = { { 2, 3, 4 }, { 4, 6, 8 } };
int
b[][] = { { 1, 5, 2, 8 }, { 5, 9, 10, -3 }, { 2, 7, -5, -18 }
};

      int [][]son = new int [s.length][s.length];

for
(int k = 0; k < a.length; k++) {
for
(int i = 0; i < b[0].length; i++) {
int
num = 0;
for
(int j = 0; j < b.length; j++) {
num +=
a[k][j] * b[j][i];
}
System.out.println(num

 

  • ” “);
    }
    System.out.println;
    }
    }

      f[0] = 1;

}

 

效果图如下:

      int sum = 1;

澳门新葡亰网址下载 6

 

七、将一个数组中的元素逆序存放。

      son[0][0] = s[0];

package
com.test;

 

import
java.util.Scanner;

      for(int i=1;i<s.length;i++){

public
class t07 {
public
static void main(String[] args) {
Scanner
sc = new Scanner(System.in);
int
arr[] = new int[20];

 

System.out.println(“请输入多个正整数:”);
int i
= 0, j;
do
{
arr[i]
= sc.nextInt();
}
while (arr[i – 1] != -1);
System.out.println(“请输入的数组为:”);
for (j
= 0; j < i – 1; j++) {
System.out.println(arr[j]

         for(int j=0;j<i;j++){

  • ” “);
    }
    System.out.println(“n数组逆序输出为:”);
    for (j
    = i – 2; j >= 0; j = j – 1) {
    System.out.println(arr[j]
  • ” “);
    }
    }

 

}

            if(s[i]>s[j]&&f[j]+1>f[i]){

八、将一个数组中的重复元素保留一个其他的清零。

 

package
com.test;

                son[i][j] = s[j];

public
class t08 {
public
static void main(String[] args) {
int[]
arr = { 1, 2, 3, 4, 5, 6, 4, 7, 2, 10 };
for
(int i = 0; i < arr.length – 1; i++) {
for
(int j = i + 1; j < arr.length; j++) {
if
(arr[i] == arr[j]) {
arr[j]
= 0;
}
}
}
}

 

}

                f[i]=f[j]+1;

九、给定一维数组{
-10,2,3,246,-100,0,5}
,计算出数组中的平均值、最大值、最小值。

 

package
com.test;

            }

public
class t09 {
public
static void main(String[] args) {
int
arr[] = new int[] { -10, 23, 246, -100, 0, 5 };
int
max = arr[0];
int
min = arr[0];
int
add = arr[0];

 

for
(int i = 0; i < arr.length; i++) {
if
(arr[i] < min) {
min =
arr[i];
} else
if (arr[i] > max) {
max =
arr[i];
}
add =
add + arr[i];
}
System.out.println(“最小值:”

         }

  • min);
    System.out.println(“最大值:”
  • max);
    System.out.println(“平均值:”
  • add / arr.length);
    }

 

}

         son[i][i] = s[i];

效果图如下:

 

澳门新葡亰网址下载 7

         if(f[i]>sum) sum=f[i];

 

      }

 

      System.out.println(“最长上升子序列的长度是 “+sum);

 

      int index = 0;

 

      int max = 0;

 

      for (int i = 0; i < son.length; i++) {

 

         int temp =0;

 

         for (int j = 0; j < son[0].length; j++) {

 

            if(son[i][j]!= 0) temp++;

 

         }

 

         if(temp>max){

 

            max = temp;

 

            index = i;

 

         }

 

      }

 

      System.out.print(“最长上升子序列是:”);

 

      for (int i = 0; i < s.length; i++) {

 

         if(son[index][i]!= 0)

 

         System.out.print(son[index][i]+” “);

 

      }

 

   }

 

}

 

    2、合唱队形

   
问题描述:N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。  
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 
则他们的身高满足T1<…<Ti>Ti+1>…>TK(1<=i<=K)。你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

分析:

首先用枚举法求出以每个人作为中间最高的同学是需要出列的同学,再在这些数据中求出最小值,即为答案。

如何求出出列的同学呢?即总人数
–留在队伍中的同学数,求留在队伍中的同学的即转换为了从左右两头求最长上升子序列问题。

代码:

public class Formation {//合唱队形问题

   public static void main(String[] args) {

      int []s={1,2,3,5,2,4,1};

      int []lenL=new int[s.length];

      int []lenR=new int[s.length];

      lenR[0]=1;

      lenL[0]=1;

      for (int i = 0; i < lenL.length; i++) {

         for (int j = 0; j < i; j++) {

            if(s[i]>s[j]&&lenL[i]<lenL[j]+1)

                lenL[i]=lenL[j]+1;

         }

      }

      for (int i = lenR.length-1; i >= 0; i–) {

         for (int j = lenR.length-1; j > i; j–) {

            if(s[i]>s[j]&&lenR[i]<lenR[j]+1)

                lenR[i]=lenR[j]+1;

         }

      }

      int len=0,x=0;

      for (int i = 0; i < lenR.length; i++) {

         if(len<lenR[i]+lenL[i]){

            len=lenR[i]+lenL[i];

            x=i;

         }

      }

      System.out.println(“需要出列”+(s.length-len)+”人”);

      System.out.println(“队伍剩余人数是”+len+”人”);

      System.out.println(“中间的同学的高度是”+s[x]);

   }

}

3、数字串加“+”的最值问题

    问题描述:设一个由0到9是个数字组成的字符串,向该  
字符串中加n个“+”,得到一个加法式,并计算得到结果。问如何添加这n个“+”使得最后的运算结果最小,输出该最小值。

分析:首先列出规划方程

F(i,j)=min[F(i-1,k)+Number(k,j)] (i<=k<j)

F(i,j)表示对于该字符串的前j个数字中添加i个加号后的最小值。

Number(i,j)表示对该字符串的第i个位置到第j个位置截取后对应的整数的值。

代码:

public class String_add_plus {

   //fun(str,i,j)表示对于str的前j个数字中添加i个加号后的最小值

   private static int fun(String str,int i,int j) {

      if(i==0){

         return Integer.parseInt(str.substring(0,j));

      }

      int min=Integer.parseInt(str);

      for(int k=i;k<j;k++){

         int
temp=fun(str,i-1,k)+Integer.parseInt(str.substring(k,j));

         if(min>temp)

            min=temp;

      }

      return min;

   }

   //测试

   public static void main(String[] args) {

      String str=”1234″;

      int min=fun(str,2,str.length());

      System.out.println(min);

   } 

}

4、子集和问题(硬币问题)

   
问题描述:设S={x1,x2,x3……xn}是一个正整数的集合,C是一个正整数,子集和问题就是判断是否存在S的一个子集S1,使得S1中元素的和为C。

    经典问题:给定11种面值分别为100元, 50元, 20元, 10元, and 5元 and
2元, 1元, 50分, 20分, 10分 and
5分的钱,现在给定一个钱数,求出可以组成的种类数。

    问题分析:

   
设c(i,j)是a1,a2……ai中包含ai且数和为j的方案数,显然目标是求c(n,T)。将前i个正整数设为阶段(1<=i<=n),将k1*a1+k2*a2+…..+ki*ai的可能数和j(ai<=j<=T)设为状态,显然状态转移方程为c(i,j)=1(i=0)或者c(i,j)=c(k,j-ai){k=1到k=i-1}的和。

 

5、最长公共子序列问题(Longest Common Subsequence,LCS)

问题描述:

首先明确最长公共子串(Longest Common
Substirng)和最长公共子序列(Longest Common
Subsequence,LCS)的区别。子串是串的一个连续的部分;子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列。也就是说,子串中字符的位置必须是连续的,子序列则可以不必连续。

分析:我们借助于一个二维棋盘来进行分析。

 

利用该棋盘逐步就可以求得一直到两个字符串的末尾时的最大子串的长度。

可以得到;

棋盘用数组s[i][j]表示,Xi,Yj表示字符串的第i、j个字符。

当i或j等于0时,s[i][j]=0;

状态转移方程是,

如果Xi==Yj,s[i][j]=max(s[i-1][j],s[i][j-1])+1;

如果Xi!=Yj,s[i][j]=max(s[i-1][j],s[i][j-1]);

代码;

public class LCS {

    private static int fun(String s1,String s2) {

       int[][]dp=new
int[s1.length()+1][s2.length()+1];

       //初始化边缘部分

       for (int i = 0; i < dp.length; i++)

           dp[i][0]=0;

       for (int j = 0; j < dp[0].length; j++)

           dp[0][j]=0;

       //状态转移运算

       for (int i = 0; i < s1.length(); i++) {

           for (int j = 0; j < s2.length(); j++) {

              if(s1.charAt(i)==s2.charAt(j))

                  dp[i+1][j+1]=dp[i][j]+1;

              else
dp[i+1][j+1]=dp[i+1][j]>dp[i][j+1]?dp[i+1][j]:dp[i][j+1];

           }

       }

       return dp[s1.length()][s2.length()];

    }

    //数据测试

    public static void main(String[] args) {

       String s1=”123qwer”,s2=”123werwer”;

       int num=fun(s1, s2);

       System.out.println(num);

    }

}

                                         
                                                             
 ——–亓慧杰                           

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图