java回溯解決,java上溯

本文目錄一覽：

• 1、java回溯和遞歸的區別，主要什麼回溯怎麼用，有代碼最好
• 2、_’ title=’回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_’>回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_
• 3、Java或者C/C++怎麼用回溯法解決最小長度電路板排列問題

java回溯和遞歸的區別，主要什麼回溯怎麼用，有代碼最好

N皇后問題的非遞歸迭代回溯法java代碼實現

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class NQueen {

static int n; // 皇后個數

static int[] x; // 當前解如{0，2，4，1，3}分別代表第1、2、3、4列的行值

static int totle; // 可行方案個數

public static void main(String[] args) {

int input = 0; //輸入n值

int sum = 0; //可行方案個數

String temp; //臨時存儲輸入值

System.out.println(“請輸入N後問題的N值：”);

try {

BufferedReader br = new BufferedReader(new InputStreamReader(

System.in));

temp = br.readLine();

input = Integer.parseInt(temp); //將輸入值轉換為int保存

if(input=0){

throw new IOException(“別輸負數好不？”);

}

System.out.println(“輸入的數是：” + input);

sum = nQueen(input); //調用nqueen方法

System.out.println(“可行方案個數為：” + sum); //輸出sum

} catch (IOException e) {

System.out.println(e.getMessage());

}catch (NumberFormatException e){

System.out.println(“請輸入數字。。。”);

}

}

private static int nQueen(int input) {

n = input; //把輸入給全局變量n

totle = 0; //初始化totle

x = new int[n + 1];

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

x[i] = 0; //初始化x

backtrack(); //調用回溯算法

return totle;

}

private static void backtrack() {

int k = 1;

while (k 0) {

x[k] += 1; //第k列皇后向下移一行

while ((x[k] = n) !(place(k))){ //如果當前第k列皇后未出界或者和其他皇后衝突

x[k] += 1; //第k列皇后向下移一行繼續尋找

System.out.println(“在第”+k+”行 “+”第”+x[k]+”列放置皇后”);

System.out.print(“當前方案為 “);

for(int i=1;i=k;i++) //打印尋找策略

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

System.out.println();

}

if (x[k] = n) //找到一個值並且未出界

if (k == n) { //已是最後一列說明已找到一個方案

totle++;

System.out.print(“可行方案為： “);

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

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

System.out.println();

} else { //不是最後一列故尋找下一列

k++;

x[k] = 0;

}

else //找到的值已經出界，回退到上一列

k–;

}

}

//判斷皇后是否衝突

private static boolean place(int k) {

for (int j = 1; j k; j++)

if ((Math.abs(k – j) == Math.abs(x[j] – x[k])) || (x[j] == x[k]))

return false;

return true;

}

}

_’>回溯法解決0-1背包問題 java寫的 求大神指點~~~~(>_

因為你把n和c 定義為static ,而且初始化為0,。數組也為靜態的,一個類中靜態的變量在這個類加載的時候就會執行，所以當你這類加載的時候，你的數組static int[] v = new int[n];

static int[] w = new int[n];

就已經初始化完畢，而且數組大小為0。在main方法里動態改變n的值是改變不了已經初始化完畢的數組的大小的，因為組已經加載完畢。

我建議你可以在定義n,c是就為其賦初值。比如（static int n=2 static int c=3）

Java或者C/C++怎麼用回溯法解決最小長度電路板排列問題

以java為例，希望能夠幫到你。

電路板排列問題

問題描述

將n塊電路板以最佳排列方式插入帶有n個插槽的機箱中。n塊電路板的不同排列方式對應於不同的電路板插入方案。設B={1, 2, …, n}是n塊電路板的集合，L={N1, N2, …, Nm}是連接這n塊電路板中若干電路板的m個連接塊。Ni是B的一個子集，且Ni中的電路板用同一條導線連接在一起。設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入的電路板編號是x[i]。x所確定的電路板排列Density (x)密度定義為跨越相鄰電路板插槽的最大連線數。

例：如圖，設n=8, m=5，給定n塊電路板及其m個連接塊：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中兩個可能的排列如圖所示，則該電路板排列的密度分別是2，3。

左上圖中，跨越插槽2和3,4和5，以及插槽5和6的連線數均為2。插槽6和7之間無跨越連線。其餘插槽之間只有1條跨越連線。在設計機箱時，插槽一側的布線間隙由電路板的排列的密度確定。因此，電路板排列問題要求對於給定的電路板連接條件(連接塊)，確定電路板的最佳排列，使其具有最小密度。

問題分析

電路板排列問題是NP難問題，因此不大可能找到解此問題的多項式時間算法。考慮採用回溯法系統的搜索問題解空間的排列樹，找出電路板的最佳排列。設用數組B表示輸入。B[i][j]的值為1當且僅當電路板i在連接塊Nj中。設total[j]是連接塊Nj中的電路板數。對於電路板的部分排列x[1:i]，設now[j]是x[1:i]中所包含的Nj中的電路板數。由此可知，連接塊Nj的連線跨越插槽i和i+1當且僅當now[j]0且now[j]！=total[j]。用這個條件來計算插槽i和i+1間的連線密度。

重點難點

算法具體實現如下：

//電路板排列問題 回溯法求解

#include “stdafx.h”

#include iostream

#include fstream

using namespace std;

ifstream fin(“5d11.txt”);

class Board

{

friend int Arrangement(int **B, int n, int m, int bestx[]);

private:

void Backtrack(int i,int cd);

int n,      //電路板數

m,      //連接板數

*x,     //當前解

*bestx,//當前最優解

bestd,  //當前最優密度

*total, //total[j]=連接塊j的電路板數

*now,   //now[j]=當前解中所含連接塊j的電路板數

**B;    //連接塊數組

};

template class Type

inline void Swap(Type a, Type b);

int Arrangement(int **B, int n, int m, int bestx[]);

int main()

{

int m = 5,n = 8;

int bestx[9];

//B={1,2,3,4,5,6,7,8}

//N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}

cout”m=”m”,n=”nendl;

cout”N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}”endl;

cout”二維數組B如下：”endl;

//構造B

int **B = new int*[n+1];

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

{

B[i] = new int[m+1];

}

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

{

for(int j=1; j=m ;j++)

{

finB[i][j];

coutB[i][j]” “;

}

coutendl;

}

cout”當前最優密度為:”Arrangement(B,n,m,bestx)endl;

cout”最優排列為：”endl;

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

{

coutbestx[i]” “;

}

coutendl;

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

{

delete[] B[i];

}

delete[] B;

return 0;

}

//核心代碼

void Board::Backtrack(int i,int cd)//回溯法搜索排列樹

{

if(i == n)

{

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

{

bestx[j] = x[j];

}

bestd = cd;

}

else

{

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

{

//選擇x[j]為下一塊電路板

int ld = 0;

for(int k=1; k=m; k++)

{

now[k] += B[x[j]][k];

if(now[k]0  total[k]!=now[k])

{

ld ++;

}

}

//更新ld

if(cdld)

{

ld = cd;

}

if(ldbestd)//搜索子樹

{

Swap(x[i],x[j]);

Backtrack(i+1,ld);

Swap(x[i],x[j]);

//恢復狀態

for(int k=1; k=m; k++)

{

now[k] -= B[x[j]][k];

}

}

}

}

}

int Arrangement(int **B, int n, int m, int bestx[])

{

Board X;

//初始化X

X.x = new int[n+1];

X.total = new int[m+1];

X.now = new int[m+1];

X.B = B;

X.n = n;

X.m = m;

X.bestx = bestx;

X.bestd = m+1;

//初始化total和now

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

{

X.total[i] = 0;

X.now[i] = 0;

}

//初始化x為單位排列並計算total

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

{

X.x[i] = i;

for(int j=1; j=m; j++)

{

X.total[j] += B[i][j];

}

}

//回溯搜索

X.Backtrack(1,0);

delete []X.x;

delete []X.total;

delete []X.now;

return X.bestd;

}

template class Type

inline void Swap(Type a, Type b)

{

Type temp=a;

a=b;

b=temp;

}

算法效率

在解空間排列樹的每個節點處，算法Backtrack花費O(m)計算時間為每個兒子節點計算密度。因此計算密度所消耗的總計算時間為O(mn!)。另外，生成排列樹需要O(n!)時間。每次更新當前最優解至少使bestd減少1，而算法運行結束時bestd=0。因此最優解被更新的額次數為O(m)。更新最優解需要O(mn)時間。綜上，解電路板排列問題的回溯算法Backtrack所需要的計算時間為O(mn!)。

程序運行結果為：