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

/*

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

*組合 回溯

*a為源數(shù)據(jù)，調(diào)用時(shí)用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背包問(wèn)題 java寫的 求大神指點(diǎn)~~~~(>_

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

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

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

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

Java或者C/C++怎么用回溯法解決最小長(zhǎng)度電路板排列問(wèn)題

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

電路板排列問(wèn)題

問(wèn)題描述

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

例：如圖，設(shè)n=8, m=5，給定n塊電路板及其m個(gè)連接塊：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};其中兩個(gè)可能的排列如圖所示，則該電路板排列的密度分別是2，3。

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

問(wèn)題分析

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

重點(diǎn)難點(diǎn)

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

//電路板排列問(wè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,?????//當(dāng)前解

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

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

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

*now,???//now[j]=當(dāng)前解中所含連接塊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"當(dāng)前最優(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)//回溯法搜索排列樹(shù)

{

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)//搜索子樹(shù)

{

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為單位排列并計(jì)算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;

}

算法效率

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

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