JAVA怎么用回溯法打印出1，2,3,4的所有組合和排列

/*

成都創(chuàng)新互聯(lián)長期為上千余家客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為裕民企業(yè)提供專業(yè)的成都做網(wǎng)站、網(wǎng)站制作，裕民網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

*組合 回溯

*a為源數(shù)據(jù)，調(diào)用時用f(a,0,"")

*/

void f(int[] a,int n,String v){

if(n==a.length){

System.out.println(v);

}else{

f(a,n+1,v);

f(a,n+1,v+","+a[n]);

}

}

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

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

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

就已經(jīng)初始化完畢，而且數(shù)組大小為0。在main方法里動態(tài)改變n的值是改變不了已經(jīng)初始化完畢的數(shù)組的大小的，因為組已經(jīng)加載完畢。

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

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

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

電路板排列問題

問題描述

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

例：如圖，設(shè)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的連線數(shù)均為2。插槽6和7之間無跨越連線。其余插槽之間只有1條跨越連線。在設(shè)計機箱時，插槽一側(cè)的布線間隙由電路板的排列的密度確定。因此，電路板排列問題要求對于給定的電路板連接條件(連接塊)，確定電路板的最佳排列，使其具有最小密度。

問題分析

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

重點難點

算法具體實現(xiàn)如下：

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

#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,??????//電路板數(shù)

m,??????//連接板數(shù)

*x,?????//當前解

*bestx,//當前最優(yōu)解

bestd,??//當前最優(yōu)密度

*total,?//total[j]=連接塊j的電路板數(shù)

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

**B;????//連接塊數(shù)組

};

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"二維數(shù)組B如下："endl;

//構(gòu)造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"當前最優(yōu)密度為:"Arrangement(B,n,m,bestx)endl;

cout"最優(yōu)排列為："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]);

//恢復(fù)狀態(tài)

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;

}

算法效率

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

程序運行結(jié)果為：

當前名稱：回溯法全排列java代碼 回溯算法全排列
網(wǎng)頁鏈接：http://m.rwnh.cn/article0/doojhoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、響應(yīng)式網(wǎng)站、品牌網(wǎng)站建設(shè)、關(guān)鍵詞優(yōu)化、企業(yè)網(wǎng)站制作、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)