動態規劃java,動態規劃java背包問題

本文目錄一覽：

• 1、~~求解~~用動態規划算法求兩數組各元素間差的最小值，JAVA代碼或方法思路
• 2、如何用動態規劃法解決最小生成樹問題
• 3、希音java面試有算法嗎
• 4、java動態規劃 計算數n由k個數相加而成的情況數
• 5、JAVA動態規劃，最長遞增子序列的代碼太難理解，求大神幫我講解一下！
• 6、java動態規劃01背包編程實現，出錯怎麼辦

~~求解~~用動態規划算法求兩數組各元素間差的最小值，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);

}

}

如何用動態規劃法解決最小生成樹問題

標題： 最小生成樹

時 限： 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動態規劃 計算數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();

    }

}

JAVA動態規劃，最長遞增子序列的代碼太難理解，求大神幫我講解一下！

第一層的 if 邏輯表示 如果新的一個數A[i]對於 B[]中的數來說是遞增的，則len加1，這是記錄遞增數列長度的主要邏輯。else中的邏輯保證B[]中的數列是最新的遞增數列。

舉個例子，如果A數組為[1,2,3,4,5, 3.1, 3.2, 3.3, 3.4]

當i=4時 len=4 B=[x,1,2,3,4,x] 循環結束後 len=5 B=[x,1,2,3,4,5] 第一層判斷走if

當i=5時 len=5 B=[x,1,2,3,4,5] 循環結束後 len=5 B=[x,1,2,3,3.1,5] 第一層判斷走else

當i=6時 len=5 B=[x,1,2,3,3.1,5] 循環結束後 len=5 B=[x,1,2,3,3.1,3.2] 第一層判斷走else

當i=7時 len=5 B=[x,1,2,3,3.1,3.2] 循環結束後 len=6 B=[x,1,2,3,3.1,3.2,3.3] 第一層判斷走else

…

其中第一層的else中做的工作就是把B從[x,1,2,3,4,5] 一步步變成 [x,1,2,3,3.1,3.2],最終B[]的最後一個元素變成3.2, 在下一次A[i]=3.3的時候，就又會走第一次if的邏輯（len加1）了。

java動態規劃01背包編程實現，出錯怎麼辦

數組下標越界.

java技術類文章可以關注微信公賬號：碼農工作室