Java五大常用算法
點擊上方藍色字體，選擇“標星公眾號”
優(yōu)質(zhì)文章，第一時間送達
算法一：分治法
基本概念
1.把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
2.分治策略是對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。
適用情況
1)該問題的規(guī)?？s小到一定的程度就可以容易地解決
2)該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
3)利用該問題分解出的子問題的解可以合并為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
分治法的復雜性分析
一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：
T（n）= k T(n/m)+f(n)
通過迭代法求得方程的解：
遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當 mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。
分治法例題：合并排序和快速排序
public class 分治_合并排序 {
/**
* 函數(shù)說明：在數(shù)組被拆分以后進行合并
*/
static void Merge(int a[], int left, int middle, int rigth) {
//定義左端數(shù)組大小
int n1 = middle - left+1;
int n2 = rigth - middle;
//初始化數(shù)組，分配內(nèi)存
int bejin[] = new int[n1];
int end[] = new int[n2];
//數(shù)組賦值
for(int i = 0; i < n1; i++)
bejin[i] = a[left + i];
for(int i = 0; i < n2; i++)
end[i] = a[middle+1+i];
//用key做原數(shù)組索引，沒調(diào)用一次函數(shù)重新給原數(shù)組付一次值
int i = 0, j = 0, key;
for(key = left; key <= rigth; key++){
if(n1>i&&n2>j&&i < n1 && bejin[i] <= end[j])
a[key] = bejin[i++];
else if(n1>i&&n2>j&&j < n2 && bejin[i] >= end[j])
a[key] = end[j++];
else if(i == n1 && j < n2)
a[key] = end[j++];
else if(j == n2 && i < n1)
a[key] = bejin[i++];
}
}
/**
* 差分數(shù)組區(qū)間，不斷分支
*/
static void MergeSort(int a[],int left,int rigth) {
int middle=0;
if(left<rigth) {
middle =(rigth+left)/2;
MergeSort(a, left, middle);
MergeSort(a, middle+1, rigth);
Merge(a, left, middle, rigth);
}
}
public static void main(String[] args) {
int a[]= {85,3,52,9,7,1,5,4};
MergeSort(a, 0,7);
for(int i=0;i<8;i++) {
System.out.print(" "+a[i]);
}
}
}
public class 分治_快速排序 {
/**
*交換函數(shù)，i，j為數(shù)組索引
*/
static void swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
/**
* 選取一個關(guān)鍵字(key)作為樞軸，一般取整組記錄的第一個數(shù)/最后一個，這里采用選取序列最后一個數(shù)為樞軸。
* 設置兩個變量left = 0;right = N - 1;
* 從left一直向后走，直到找到一個大于key的值，right從后至前，直至找到一個小于key的值，然后交換這兩個數(shù)。
* 重復第三步，一直往后找，直到left和right相遇，這時將key放置left的位置即可。
* @return
*/
static int PartSort(int[] array,int left,int right)
{
int key = array[right];//定義基準
int count=right;//保存rigth值
while(left < right)//防止數(shù)組越界
{
while(left < right && array[left] <= key)
{
++left;
}
while(left < right && array[right] >= key)
{
--right;
}
swap(array,left,right);
}
swap(array,right,count);
return right;
}
/**
*分治思想，遞歸調(diào)用
*/
static void QuickSort(int array[],int left,int right)
{
if(left >= right)//表示已經(jīng)完成一個組
{
return;
}
int index = PartSort(array,left,right);//樞軸的位置
QuickSort(array,left,index - 1);
QuickSort(array,index + 1,right);
}
public static void main(String[] args) {
int a[]= {1,5,-5,54,15,67,16,23};
QuickSort(a,0,7);
for(int i=0;i<a.length;i++) {
System.out.print(" "+a[i]);
}
System.out.print("\n");
}
}
算法心得
作為分治法里很典型的一種算法，合并排序和快速排序充分展現(xiàn)了分治法的思想，分而治之，在此次編程使用此方法中，給我的體會是程序簡單分為兩部分，第一部分，不斷“拆”，縮小子問題規(guī)模，達到最優(yōu)子結(jié)構(gòu)。然后合并，在合并過程中，應為子問題足夠小，容易計算，再者不斷合并子問題答案，最終求出問題解。
算法二：貪心算法
一、基本概念：
所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
貪心算法沒有固定的算法框架，算法設計的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關(guān)。
所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性。
二、貪心算法的基本思路：
1.建立數(shù)學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優(yōu)解。
4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。
三、貪心算法適用的問題
貪心策略適用的前提是：局部最優(yōu)策略能導致產(chǎn)生全局最優(yōu)解。
實際上，貪心算法適用的情況很少。一般，對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數(shù)據(jù)進行分析，就可做出判斷。
四、貪心算法的實現(xiàn)框架
從問題的某一初始解出發(fā)；
while （能朝給定總目標前進一步）
{
利用可行的決策，求出可行解的一個解元素；
}
由所有解元素組合成問題的一個可行解；
五、貪心策略的選擇
因為用貪心算法只能通過解局部最優(yōu)解的策略來達到全局最優(yōu)解，因此，一定要注意判斷問題是否適合采用貪心算法策略，找到的解是否一定是問題的最優(yōu)解。
貪心策略例題：prim算法
import java.util.*;
public class 貪心算法_prim算法 {
static int MAX = Integer.MAX_VALUE;
public static void main(String[] args) {
//定義無向圖矩陣
int[][] map = new int[][] {
{ 0, 1, 6, 2},
{ 1, 0, 3, 2},
{ 6, 3, 0, 1},
{ 2, 2, 1, 0}
};
prim(map, map.length);
}
public static void prim(int[][] graph, int n){
//定義節(jié)點名字
char[] c = new char[]{'A','B','C','D'};
int[] lowcost = new int[n]; //到新集合的最小權(quán)
int[] mid= new int[n];//存取前驅(qū)結(jié)點
List<Character> list=new ArrayList<Character>();//用來存儲加入結(jié)點的順序
int i, j, min, minid , sum = 0;
//初始化輔助數(shù)組
for(i=1;i<n;i++)
{
lowcost[i]=graph[0][i];
mid[i]=0;
}
list.add(c[0]);
//一共需要加入n-1個點
for(i=1;i<n;i++)
{
min=MAX;
minid=0;
//每次找到距離集合最近的點
for(j=1;j<n;j++)
{
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j];
minid=j;
}
}
if(minid==0) return;
list.add(c[minid]);
lowcost[minid]=0;
sum+=min;
System.out.println(c[mid[minid]] + "到" + c[minid] + " 權(quán)值：" + min);
//加入該點后，更新其它點到集合的距離
for(j=1;j<n;j++)
{
if(lowcost[j]!=0&&lowcost[j]>graph[minid][j])
{
lowcost[j]=graph[minid][j];
mid[j]=minid;
}
}
System.out.print("\n");
}
System.out.println("sum:" + sum);
}
}
算法心得
Prim算法是貪婪策略的一種很好的體現(xiàn)，在實現(xiàn)prim算法中，認識到，貪婪策略是在做當先選擇的情況下，先行囊括所有的選擇儲存好，在根據(jù)貪婪策略，選出最符合的步驟進行下去。雖然貪婪策略比較迅捷，應為它不需要預算所有情況（類似回溯），但應為每次所求只是局部最優(yōu)解，所以結(jié)果不一定是最優(yōu)解，算法準確性在與貪婪策略的選取好壞，所以也具有一定的局限性！
算法三：動態(tài)規(guī)劃算法
一、基本概念
動態(tài)規(guī)劃過程是：每次決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃。
二、基本思想與策略
基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。
由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。
與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。
三、適用的情況
能采用動態(tài)規(guī)劃求解的問題的一般要具有3個性質(zhì)：
(1) 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。
(2) 無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關(guān)。
（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）
算法實例：背包問題
public class 動態(tài)規(guī)劃_背包問題 {
public static void main(String[] args) {
//物品價值,重量,和背包承重
int v[]={0,8,10,6,3,7,2};
int w[]={0,4,6,2,2,5,1};
int c=12;
//定義二位數(shù)組動態(tài)規(guī)劃背包價值和重量
int m[][]=new int[v.length][c+1];
for (int i = 1; i <v.length; i++) {
for (int j = 1; j <=c; j++) {
if(j>=w[i])
m[i][j]=m[i-1][j-w[i]]+v[i]>m[i-1][j]?m[i-1][j-w[i]]+v[i]:m[i-1][j];
else
m[i][j]=m[i-1][j];
}
}
int max=0;
for (int i = 0; i <v.length; i++) {
for (int j = 0; j <=c; j++) {
if(m[i][j]>max)
max=m[i][j];
}
}
System.out.println(max);
}
}
四、算法心得
在此次編程中，運用動態(tài)內(nèi)存算法解決背包問題，發(fā)先所需分配空間量比較大，在做背包容量小，物平少時還好。如果涉及數(shù)量打一是內(nèi)存占用會比較嚴重，計算量也會大大提高。動態(tài)分配內(nèi)存類似分治法，把問題分成多個子問題，一步步求解，且前面求出的子問題會對后面所求子問題有影響，不像是分治法的子問題都是獨立的。并且時刻給與一個狀態(tài)值，記錄最優(yōu)解，當所有子問題都解決完時，最優(yōu)解也就會成為了問題的解了。重點主要在于對內(nèi)存的分配，和子問題的計算。
算法四：回溯法
1、概念
回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。
回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。
許多復雜的，規(guī)模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。
2、基本思想
在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點出發(fā)深度探索解空間樹。當探索到某一結(jié)點時，要先判斷該結(jié)點是否包含問題的解，如果包含，就從該結(jié)點出發(fā)繼續(xù)探索下去，如果該結(jié)點不包含問題的解，則逐層向其祖先結(jié)點回溯。（其實回溯法就是對隱式圖的深度優(yōu)先搜索算法）。
若用回溯法求問題的所有解時，要回溯到根，且根結(jié)點的所有可行的子樹都要已被搜索遍才結(jié)束。
而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束。
3、用回溯法解題的一般步驟：
（1）針對所給問題，確定問題的解空間：
首先應明確定義問題的解空間，問題的解空間應至少包含問題的一個（最優(yōu)）解。
（2）確定結(jié)點的擴展搜索規(guī)則
（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。
4、算法實例：求子集問題
public class 回溯法_求子集問題 {
private static int[] s = {2,2,3};
private static int n = s.length;
private static int[] x = new int[n];
/**
* 輸出集合的子集
* @param limit 決定選出特定條件的子集
* 注：all為所有子集,num為限定元素數(shù)量的子集,
* sp為限定元素奇偶性相同，且和小于8。
*/
public static void all_subset(String limit){
switch(limit){
case "all":backtrack(0);break;
case "num":backtrack1(0);break;
case "sp":backtrack2(0);break;
}
}
/**
* 回溯法求集合的所有子集，依次遞歸
* 注：是否回溯的條件為精髓
* @param t
*/
private static void backtrack(int t){
if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {
x[t] = i;
backtrack(t+1);
}
}
/**
* 回溯法求集合的所有(元素個數(shù)小于4)的子集，依次遞歸
* @param t
*/
private static void backtrack1(int t){
if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {
x[t] = i;
if(count(x, t) < 4)
backtrack1(t+1);
}
}
/**
* (剪枝)
* 限制條件：子集元素小于4,判斷0~t之間已被選中的元素個數(shù)，
* 因為此時t之后的元素還未被遞歸,即決定之后的元素
* 是否應該被遞歸調(diào)用
* @param x
* @param t
* @return
*/
private static int count(int[] x, int t) {
int num = 0;
for (int i = 0; i <= t; i++) {
if(x[i] == 1){
num++;
}
}
return num;
}
/**
* 回溯法求集合中元素奇偶性相同，且和小于8的子集,依次遞歸
* @param t
*/
private static void backtrack2(int t){
if(t >= n)
output(x);
else
for (int i = 0; i <= 1; i++) {
x[t] = i;
if(legal(x, t))
backtrack2(t+1);
}
}
/**
* 對子集中元素奇偶性進行判斷，還需元素的數(shù)組和小于8
* @param x
* @param t
* @return
*/
private static boolean legal(int[] x, int t) {
boolean bRet = true; //判斷是否需要剪枝
int part = 0; //奇偶性判斷的基準
for (int i = 0; i <= t; i++) { //選擇第一個元素作為奇偶性判斷的基準
if(x[i] == 1){
part = i;
break;
}
}
for (int i = 0; i <= t; i++) {
if(x[i] == 1){
bRet &= ((s[part] - s[i]) % 2 == 0);
}
}
int sum = 0;
for(int i = 0; i <= t; i++){
if(x[i] == 1)
sum += s[i];
}
bRet &= (sum < 8);
return bRet;
}
/**
* 子集輸出函數(shù)
* @param x
*/
private static void output(int[] x) {
for (int i = 0; i < x.length; i++) {
if(x[i] == 1){
System.out.print(s[i]);
}
}
System.out.println();
}
public static void main(String[] args) {
all_subset("all");
}
}
5、算法心得
回溯法是一種幾乎萬能的算法，無論面對規(guī)模大還是規(guī)模小的問題都有妙用，在此次求子集問題中，回溯法的妙用我認為有兩點，一是它采用深度優(yōu)先遍歷算法，可以從根節(jié)點訪問到所有子節(jié)點，也就有了剪枝的妙用，在進有行奇偶限制，求和限制時，可以很好的做到把這些“越界”的沒必要的子節(jié)點及子節(jié)點后的孫子節(jié)點去掉，大大減少了時間的浪費性。二是，算法框架的簡潔性，使使用者能非常清晰的明白代碼進行的方式。
算法五：分支限界法
一、基本描述
類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標不同。回溯法的求解目標是找出T中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解，即在某種意義下的最優(yōu)解。
（1）分支搜索算法
所謂“分支”就是采用廣度優(yōu)先的策略，依次搜索E-結(jié)點的所有分支，也就是所有相鄰結(jié)點，拋棄不滿足約束條件的結(jié)點，其余結(jié)點加入活結(jié)點表。然后從表中選擇一個結(jié)點作為下一個E-結(jié)點，繼續(xù)搜索。
選擇下一個E-結(jié)點的方式不同，則會有幾種不同的分支搜索方式。
1）FIFO搜索
2）LIFO搜索
3）優(yōu)先隊列式搜索
（2）分支限界搜索算法
二、分支限界法的一般過程
由于求解目標不同，導致分支限界法與回溯法在解空間樹T上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹T。
分支限界法的搜索策略是：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當前的活結(jié)點表中選擇下一個擴展對點。為了有效地選擇下一擴展結(jié)點，以加速搜索的進程，在每一活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作為擴展結(jié)點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。
分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結(jié)點所使用的擴展方式不同。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，那些導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被子加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所求的解或活結(jié)點表為空時為止。
三、回溯法和分支限界法的一些區(qū)別
有一些問題其實無論用回溯法還是分支限界法都可以得到很好的解決，但是另外一些則不然。也許我們需要具體一些的分析——到底何時使用分支限界而何時使用回溯呢？
回溯法和分支限界法的一些區(qū)別：
方法對解空間樹的搜索方式 存儲結(jié)點的常用數(shù)據(jù)結(jié)構(gòu)結(jié)點存儲特性常用應用
回溯法深度優(yōu)先搜索堆?；罱Y(jié)點的所有可行子結(jié)點被遍歷后才被從棧中彈出找出滿足約束條件的所有解
分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊列、優(yōu)先隊列每個結(jié)點只有一次成為活結(jié)點的機會找出滿足約束條件的一個解或特定意義下的最優(yōu)解
import java.util.Collections;
import java.util.LinkedList;
public class 分支界限法_求最大承重問題 {
LinkedList<HeapNode> heap;
public static class BBnode{
BBnode parent;//父結(jié)點
boolean leftChild;//左兒子結(jié)點標志
//構(gòu)造方法
public BBnode(BBnode par,boolean ch){
parent=par;
leftChild=ch;
}
}
/**
* 輸出函數(shù)，做調(diào)試用
* @param list
*/
public static void printReverse(LinkedList<HeapNode> list){
for (int i=0;i<list.size();i++) {
HeapNode aBnode=list.get(i);
System.out.print("#"+aBnode.uweight+"#"+aBnode.level+" ");
}
}
/*
* 最大優(yōu)先隊列中存儲的活結(jié)點類型為HeapNode
*/
public static class HeapNode implements Comparable{
BBnode liveNode;
int uweight;//活結(jié)點優(yōu)先級（上界）
int level;//活結(jié)點在子集樹種所處的層序號
//構(gòu)造函數(shù)
public HeapNode(BBnode node,int up,int lev){
liveNode=node;
uweight=up;
level=lev;
}
@Override
public int compareTo(Object x) {//升序排列
int xu=((HeapNode)x).uweight;
if(uweight<xu) return -1;
if(uweight==xu) return 0;
return 1;
}
public boolean equals(Object x){
return uweight==((HeapNode)x).uweight;
}
}
public void addLiveNode(int up,int lev,BBnode par,boolean ch){
//將活結(jié)點加入到表示活結(jié)點優(yōu)先隊列的最大堆H中
BBnode b=new BBnode(par,ch);
HeapNode node=new HeapNode(b,up,lev);
heap.add(node);
Collections.sort(heap);
}
public int maxLoading(int[] w,int c,int[] bestx){
int count=0;
//優(yōu)先隊列式分支限界法，返回最優(yōu)重量，bestx返回最優(yōu)解
heap=new LinkedList<HeapNode>();
int n=w.length-1;
BBnode e=null;//當前擴展結(jié)點
int i=1;//當前擴展結(jié)點所處的層
int ew=0;//擴展結(jié)點所對應的載重量
//定義剩余重量數(shù)組r
int[] r=new int[n+1];
for(int j=n-1;j>0;j--) {
r[j]=r[j+1]+w[j+1];
}
//搜索子集空間樹
while(i!=n+1){
//非葉結(jié)點
//檢查當前擴展結(jié)點的兒子結(jié)點
if(ew+w[i]<=c){
//左兒子結(jié)點為可行結(jié)點
addLiveNode(ew+w[i]+r[i],i+1,e,true);
}
//右兒子結(jié)點總為可行結(jié)點
addLiveNode(ew+r[i],i+1,e,false);
//printReverse(heap);
//取下一個結(jié)點
HeapNode node=heap.pollLast();
i=node.level;
e=node.liveNode;
ew=node.uweight-r[i-1];
}
//輸出
for(int j=0;j<n;j++){
bestx[j]=(e.leftChild)?1:0;
e=e.parent;
}
for(int j=n-1;j>=0;j--){
System.out.print(bestx[j]+" ");
}
System.out.println();
return ew;
}
public static void main(String[] args) {
int n=4;
int c=70;
int w[]={0,26,60,22,18};//下標從1開始
int[] bestx=new int[n+1];
分支界限法_求最大承重問題 b=new 分支界限法_求最大承重問題();
System.out.println("最優(yōu)裝載順序為（1表示裝入，0表示未裝入）：");
int ew=b.maxLoading(w, c, bestx);
System.out.println("最優(yōu)裝載重量為："+ew);
}
}
————————————————
版權(quán)聲明：本文為CSDN博主「我去灬買橘子」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：
https://blog.csdn.net/qq_39147389/article/details/82252924
鋒哥最新SpringCloud分布式電商秒殺課程發(fā)布
??????
??長按上方微信二維碼 2 秒
感謝點贊支持下哈 