「动态规划算法java」动态规划算法java完全背包

本篇文章给大家谈谈动态规划算法java，以及动态规划算法java完全背包对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、~~求解~~用动态规划算法求两数组各元素间差的最小值，JAVA代码或方法思路
• 2、java动态规划 计算数n由k个数相加而成的情况数
• 3、可用动态规划算法解决的问题可能不能用贪心算法
• 4、java语言中编程求解两个字符串最长相同字符串的长度
• 5、如何用动态规划法解决最小生成树问题
• 6、希音java面试有算法吗

~~求解~~用动态规划算法求两数组各元素间差的最小值，JAVA代码或方法思路

import java.util.Arrays;

public class Test {

public static void getCha(int [] a,int []b){

int min =Integer.MAX_VALUE;

int sss=0;

int kkk = 0;

int c = 0;

int d = 0;

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

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

int temp = Math.abs(a[i]-b[j]);

if(tempmin){

min = temp;

sss = a[i];

kkk = b[j];

c=i;

d=j;

}

}

}

System.out.println("最大差距："+min+"数组A["+c+"]"+sss+"数组B["+d+"]"+kkk);

}

public static void main(String[] args) {

int []a = new int[8];

int []b = new int[12];

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

a[i] = (int)( Math.random()*100);

}

System.out.println(Arrays.toString(a));;

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

b[i] = (int) (Math.random()*100);

}

System.out.println(Arrays.toString(b));

getCha(a,b);

}

}

java动态规划 计算数n由k个数相加而成的情况数

public class MyClass {

    public static void main(String[] args) {

        System.out.println(" result count:" + method(6, 3));

    }

    public static int method(int n, int k) {

        ListListInteger list = new ArrayList();

        for (int i = 0; i  k; i++) {

            if (i == 0) {

                for (int j = 1; j  n; j++) {

                    ListInteger li = new ArrayList();

                    li.add(j);

                    list.add(li);

                }

                continue;

            }

            ListListInteger listNew = new ArrayList();

            for (ListInteger integers : list) {

                for (int j = integers.get(integers.size() - 1); j  n; j++) {

                    ListInteger li = new ArrayList();

                    li.addAll(integers);

                    li.add(j);

                    listNew.add(li);

                    if (i + 1 == k) {

                        int res = 0;

                        for (Integer integer : li) {

                            res += integer;

                        }

                        if (res != n) {

                            listNew.remove(li);

                        }

                    }

                }

            }

            list.clear();

            list.addAll(listNew);

        }

        for (ListInteger integers : list) {

            for (Integer integer : integers) {

                System.out.print(integer + "\t");

            }

            System.out.println();

        }

        return list.size();

    }

}

可用动态规划算法解决的问题可能不能用贪心算法

主要涉及到以下几个方面的内容：

①什么是活动选择问题---粗略提下，详细请参考《算法导论》

②活动选择问题的DP(Dynamic

programming)求解--DP求解问题的思路

③活动选择问题的贪心算法求解

④为什么这个问题可以用贪心算法求解？

⑤动态规划与贪心算法的一些区别与联系

⑥活动选择问题的DP求解的JAVA语言实现以及时间复杂度分析

⑦活动选择问题的Greedy算法JAVA实现和时间复杂度分析

⑧一些有用的参考资料

java语言中编程求解两个字符串最长相同字符串的长度

public class StringTest4 {

/**

* @param args

*/

public static void main(String[] args) {

/*

* 需求4：两个字符串的最大相同子串。

* "sadfcctvghjkl"

* "zxcctvcv"

*

* 思路：

* 1，以短的字符串为主。

* 到长的字符串中去判断是否存在，如果存在，已找到。

* 2，如果没有找到。将短的字符串的长度递减获取子串继续到长的串中查找。只要找到就结束。

* 3，没有找到，说明没有相同的。

*

*/

String s1 = "sadfcctvghjkl";

String s2 = "zxcctvcv";

String maxSub = getMaxSubString(s2,s1);

System.out.println("maxsub="+maxSub+" length="+maxSub.length());

}

public static String getMaxSubString(String s1, String s2) {

//确定哪个是长的哪个是短的。

String longStr,shortStr;

longStr = s1.length()s2.length()?s1:s2;

shortStr = s1.equals(longStr)?s2:s1;

// System.out.println("long:"+longStr);

// System.out.println("short:"+shortStr);

//对短的字符串操作，从短串中取子串，到长字符串中判断，是否存在。

for(int x=0; xshortStr.length(); x++){

for(int y=0,z=shortStr.length()-x; z=shortStr.length(); y++,z++){

//根据y，z，获取子串。

String temp = shortStr.substring(y,z);

// System.out.println(temp);

if(longStr.contains(temp))

return temp;

}

}

return null;

}

}

如何用动态规划法解决最小生成树问题

标题： 最小生成树

时 限： 1000 ms

内存限制： 10000 K

总时限： 3000 ms

描述：

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。假定所有输入的根节点或者源为第一个城市或第一组数据。

请使用prim算法求解。

输入：

n（城市数，1=n=100）；

e（边数）；

以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。

输出：

n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。

输入样例：

5

8

1 2 2

1 3 12

1 4 10

2 3 8

2 5 9

3 4 6

3 5 3

4 5 7

输出样例：

1 2

2 3

3 5

3 4

提示：

import java.util.Scanner;

public class Main {

public static void prim(int n,float [][]c)

{

float []lowcost = new float [n+1];

int [] closest = new int [n+1];

boolean [] s = new boolean [n+1];

s[1] = true;

for(int i=2;i=n;i++)

{

lowcost[i] = c[1][i];

closest[i] = 1;

s[i] = false ;

}

for(int i=1;in;i++)

{

float min = Float.MAX_VALUE;

int j =1;

for(int k =2;k=n;k++)

if((lowcost[k]min)(!s[k]))

{

min = lowcost[k];

j =k;

}

System.out.println(closest[j]+" "+j);

s[j] = true;

for(int k =2; k=n;k++)

if((c[j][k]lowcost[k])(!s[k]))

{

lowcost[k] = c[j][k];

closest[k] = j;

}

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n =sc.nextInt();

int m = sc.nextInt();

float [][]c = new float [n+1][n+1];

for(int i = 0;im ;i++)

{

int x =sc.nextInt();

int y = sc.nextInt();

float z = sc.nextFloat();

c[x][y] = z;

}

for(int i =0;i=n;i++)

for(int j =0;j=n;j++)

if(c[i][j]==0)

c[i][j] =Float.MAX_VALUE;

希音java面试有算法吗

有。常见的如下：

一是字符串，如果IDE没有代码自动补全功能，所以你应该记住下面的这些方法。

二是链表，在Java中，链表的实现非常简单，每个节点Node都有一个值val和指向下个节点的链接next。链表两个著名的应用是栈Stack和队列Queue。

三是树，这里的树通常是指二叉树，每个节点都包含一个左孩子节点和右孩子节点。

四是排序，五是递归vs.迭代。

六是动态规划，动态规划是解决下面这些性质类问题的技术：一个问题可以通过更小子问题的解决方法来解决（即问题的最优解包含了其子问题的最优解，也就是最优子结构性质）。

有些子问题的解可能需要计算多次（也就是子问题重叠性质）。子问题的解存储在一张表格里，这样每个子问题只用计算一次。需要额外的空间以节省时间。爬台阶问题完全符合上面的四条性质，因此可以用动态规划法来解决。

动态规划算法java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于动态规划算法java完全背包、动态规划算法java的信息别忘了在本站进行查找喔。