三維裝箱演算法

❶ 裝箱問題、裝箱演算法

裝箱問題一般都是通過貪心演算法來求解的。隨便翻本數據結構的書上都會有詳細的介紹。網上也一定很多，自己找找哈。大概的思路是這樣的：

//依次將零件放到它第一個能放下的箱中，設11種零件的尺寸是按從大到小的順序排列（可以先對11種零件按尺寸大小從大到小排序），然後按排序結果對零件重新編號。

簡單地用偽代碼描述下演算法吧：

{
輸入箱子的尺寸；
按零件尺寸把11種零件從大到小排列，輸入各尺寸。
預置已用箱子鏈為空；
預置已用箱子計數器count為0；
for(i=0;i<n;i++)
{
從已用的第一隻箱子開始順序尋找能放入零件i的箱子j；
if(已用箱子都不能再放下零件i)
{
另用一隻箱子，並將零件i放入該箱子；
count++;
}
else 將零件i放入箱子j；
}
}

❷ 裝箱問題的BFD演算法

NP不完全問題只給0分是沒人做的,給200分做恐怕都很難呀.
我做過二維的NP排料問題,很麻煩的.三維的要更難了!
祝你好運!

❸ 集裝箱最優裝櫃計算方法

20尺集裝箱內徑：5.89x2.34x2.38（長寬高）
40尺集裝箱內徑：12,03x2.34x2.38
用你的包裝箱尺寸，去吻合集裝箱的長寬高，一定要小於集裝箱的長寬高。即可。
例：
高：1.140x2層=2.28m，小於集裝箱的高。
寬：1.080x2排=2.160m,小於集裝箱的寬。
長：0.5x11排=5.5m
,
小於集裝箱的長。
長寬高都可以保證裝進去。
數量：2x2x11=44箱。
提示：40尺集裝箱長12.03m，理論裝24排，但是實際上在長度方向，一定會漲箱，保證裝不進去。（這是實際經驗），只能按照23排計算。
40尺可裝數量：2x2x23=92箱。
祝你好運！

❹ Python 如何將長度不同的字元串盡量均勻地分配到N個文件中每一行的字元串作為整體，不能打散。

背包問題的一個變種。或者說是一維裝箱演算法。

你將每一行字元串想像為一個物品，字元串的長度就是這個物品的大小。每個文件相當於不同的箱子，箱子的大小是固定的，裝入的物品體積之和不能超過箱子的總容量。

問題就是：如何使用盡可能少的箱子來裝入所有的物品，或者：如果使盡可能多的箱子空間利用率更高，以及類似的相關問題。

這類問題的答案不是一個簡單的數字，它需要給出一個策略：物品1...n分別裝入箱子1...m(m<=n).

對於二維裝箱或三維等，區別主要在於解法的復雜度，但一個解法一般來說其思路是可以從一維擴展到二維或者三維的。

這類問題目前來說，沒有全局最優解（即，沒有一個演算法能確保在所有情況下均能得到最好的結果），但可以得到局部最優解。演算法有多種，如最常見的貪心演算法，或動態規劃。

貪心演算法的思路比較簡單：把所有的物品從大到小排好序，拿一個箱子，嘗試裝入最大的物品，如果不能裝入，就嘗試裝入小一些的物品，如此循環，直到所有物品裝入所有箱子。

演算法很簡單，但很多時候得到的結果並不理想。

❺ 簡述演算法的各種表示形式

一、什麼是演算法

演算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。演算法常常含有重復的步驟和一些比較或邏輯判斷。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time Complexity）。時間復雜度用「O（數量級）」來表示，稱為「階」。常見的時間復雜度有： O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。

演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。

二、演算法設計的方法

1.遞推法

遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。設要求問題規模為N的解，當N=1時，解或為已知，或能非常方便地得到解。能採用遞推法構造演算法的問題有重要的遞推性質，即當得到問題規模為i-1的解後，由問題的遞推性質，能從已求得的規模為1，2，…，i-1的一系列解，構造出問題規模為I的解。這樣，程序可從i=0或i=1出發，重復地，由已知至i-1規模的解，通過遞推，獲得規模為i的解，直至得到規模為N的解。

【問題】 階乘計算

問題描述：編寫程序，對給定的n（n≤100），計算並輸出k的階乘k！（k=1，2，…，n）的全部有效數字。

由於要求的整數可能大大超出一般整數的位數，程序用一維數組存儲長整數，存儲長整數數組的每個元素只存儲長整數的一位數字。如有m位成整數N用數組a[ ]存儲：

N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100

並用a[0]存儲長整數N的位數m，即a[0]=m。按上述約定，數組的每個元素存儲k的階乘k！的一位數字，並從低位到高位依次存於數組的第二個元素、第三個元素……。例如，5！=120，在數組中的存儲形式為：

3 0 2 1 ……

首元素3表示長整數是一個3位數，接著是低位到高位依次是0、2、1，表示成整數120。

計算階乘k！可採用對已求得的階乘(k-1)！連續累加k-1次後求得。例如，已知4！=24，計算5！，可對原來的24累加4次24後得到120。細節見以下程序。

# include <stdio.h>

# include <malloc.h>

# define MAXN 1000

void pnext(int a[ ],int k)

{ int *b,m=a[0],i,j,r,carry;

b=(int * ) malloc(sizeof(int)* (m+1));

for ( i=1;i<=m;i++) b[i]=a[i];

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

{ for ( carry=0,i=1;i<=m;i++)

{ r=(i<a[0]?a[i]+b[i]:a[i])+carry;

a[i]=r%10;

carry=r/10;

}

if (carry) a[++m]=carry;

}

free(b);

a[0]=m;

}

void write(int *a,int k)

{ int i;

printf(「%4d！=」,k);

for (i=a[0];i>0;i--)

printf(「%d」,a[i]);

printf(「\n\n」);

}

void main()

{ int a[MAXN],n,k;

printf(「Enter the number n: 「);

scanf(「%d」,&n);

a[0]=1;

a[1]=1;

write(a,1);

for (k=2;k<=n;k++)

{ pnext(a,k);

write(a,k);

getchar();

}

}

2.遞歸

遞歸是設計和描述演算法的一種有力的工具，由於它在復雜演算法的描述中被經常採用，為此在進一步介紹其他演算法設計方法之前先討論它。

能採用遞歸描述的演算法通常有這樣的特徵：為求解規模為N的問題，設法將它分解成規模較小的問題，然後從這些小問題的解方便地構造出大問題的解，並且這些規模較小的問題也能採用同樣的分解和綜合方法，分解成規模更小的問題，並從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。

【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。

斐波那契數列為：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) （當n>1時）。

寫成遞歸函數有：

int fib(int n)

{ if (n==0) return 0;

if (n==1) return 1;

if (n>1) return fib(n-1)+fib(n-2);

}

遞歸演算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小於n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。

在回歸階段，當獲得最簡單情況的解後，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)後，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果後，返回得到fib(n)的結果。

在編寫遞歸函數時要注意，函數中的局部變數和參數知識局限於當前調用層，當遞推進入「簡單問題」層時，原來層次上的參數和局部變數便被隱蔽起來。在一系列「簡單問題」層，它們各有自己的參數和局部變數。

由於遞歸引起一系列的函數調用，並且可能會有一系列的重復計算，遞歸演算法的執行效率相對較低。當某個遞歸演算法能較方便地轉換成遞推演算法時，通常按遞推演算法編寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應採用遞推演算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求的第n項。

【問題】 組合問題

問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為： （1）5、4、3 （2）5、4、2 （3）5、4、1

（4）5、3、2 （5）5、3、1 （6）5、2、1

（7）4、3、2 （8）4、3、1 （9）4、2、1

（10）3、2、1

分析所列的10個組合，可以採用這樣的遞歸思想來考慮求組合函數的演算法。設函數為void comb(int m,int k)為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其後的數字是從餘下的m-1個數中取k-1數的組合。這就將求m個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函數引入工作數組a[ ]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出後，才將a[ ]中的一個組合輸出。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組後，有兩種可能的選擇，因還未去頂組合的其餘元素，繼續遞歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數comb。

【程序】

# include <stdio.h>

# define MAXN 100

int a[MAXN];

void comb(int m,int k)

{ int i,j;

for (i=m;i>=k;i--)

{ a[k]=i;

if (k>1)

comb(i-1,k-1);

else

{ for (j=a[0];j>0;j--)

printf(「%4d」,a[j]);

printf(「\n」);

}

}

}

void main()

{ a[0]=3;

comb(5,3);

}

3.回溯法

回溯法也稱為試探法，該方法首先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。

【問題】 組合問題

問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。

採用回溯法找問題的解，將找到的組合以從小到大順序存於a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：

（1） a[i+1]>a[i]，後一個數字比前一個大；

（2） a[i]-i<=n-r+1。

按回溯法的思想，找解過程可以敘述如下：

首先放棄組合數個數為r的條件，候選組合從只有一個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，並使其滿足上述條件（1），候選組合改為1，2。繼續這一過程，得到候選組合1，2，3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4，以及以後調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由於對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，並向前試探，得到解1，3，4。重復上述向前試探和向後回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程序如下：

【程序】

# define MAXN 100

int a[MAXN];

void comb(int m,int r)

{ int i,j;

i=0;

a[i]=1;

do {

if (a[i]-i<=m-r+1

{ if (i==r-1)

{ for (j=0;j<r;j++)

printf(「%4d」,a[j]);

printf(「\n」);

}

a[i]++;

continue;

}

else

{ if (i==0)

return;

a[--i]++;

}

} while (1)

}

main()

{ comb(5,3);

}

4.貪婪法

貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

例如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪演算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。

【問題】 裝箱問題

問題描述：裝箱問題可簡述如下：設有編號為0、1、…、n-1的n種物品，體積分別為v0、v1、…、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過V，即對於0≤i＜n，有0＜vi≤V。不同的裝箱方案所需要的箱子數目可能不同。裝箱問題要求使裝盡這n種物品的箱子數要少。

若考察將n種物品的集合分劃成n個或小於n個物品的所有子集，最優解就可以找到。但所有可能劃分的總數太大。對適當大的n，找出所有可能的劃分要花費的時間是無法承受的。為此，對裝箱問題採用非常簡單的近似演算法，即貪婪法。該演算法依次將物品放到它第一個能放進去的箱子中，該演算法雖不能保證找到最優解，但還是能找到非常好的解。不失一般性，設n件物品的體積是按從大到小排好序的，即有v0≥v1≥…≥vn-1。如不滿足上述要求，只要先對這n件物品按它們的體積從大到小排序，然後按排序結果對物品重新編號即可。裝箱演算法簡單描述如下：

{ 輸入箱子的容積；

輸入物品種數n；

按體積從大到小順序，輸入各物品的體積；

預置已用箱子鏈為空；

預置已用箱子計數器box_count為0；

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

{ 從已用的第一隻箱子開始順序尋找能放入物品i 的箱子j；

if （已用箱子都不能再放物品i）

{ 另用一個箱子，並將物品i放入該箱子；

box_count++；

}

else

將物品i放入箱子j；

}

}

上述演算法能求出需要的箱子數box_count，並能求出各箱子所裝物品。下面的例子說明該演算法不一定能找到最優解，設有6種物品，它們的體積分別為：60、45、35、20、20和20單位體積，箱子的容積為100個單位體積。按上述演算法計算，需三隻箱子，各箱子所裝物品分別為：第一隻箱子裝物品1、3；第二隻箱子裝物品2、4、5；第三隻箱子裝物品6。而最優解為兩只箱子，分別裝物品1、4、5和2、3、6。

若每隻箱子所裝物品用鏈表來表示，鏈表首結點指針存於一個結構中，結構記錄尚剩餘的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構成鏈表。以下是按以上演算法編寫的程序。

【程序】

# include <stdio.h>

# include <stdlib.h>

typedef struct ele

{ int vno;

struct ele *link;

} ELE;

typedef struct hnode

{ int remainder;

ELE *head;

Struct hnode *next;

} HNODE;

void main()

{ int n, i, box_count, box_volume, *a;

HNODE *box_h, *box_t, *j;

ELE *p, *q;

Printf(「輸入箱子容積\n」);

Scanf(「%d」,&box_volume);

Printf(「輸入物品種數\n」);

Scanf(「%d」,&n);

A=(int *)malloc(sizeof(int)*n);

Printf(「請按體積從大到小順序輸入各物品的體積：」);

For (i=0;i<n;i++) scanf(「%d」,a+i);

Box_h=box_t=NULL;

Box_count=0;

For (i=0;i<n;i++)

{ p=(ELE *)malloc(sizeof(ELE));

p->vno=i;

for (j=box_h;j!=NULL;j=j->next)

if (j->remainder>=a[i]) break;

if (j==NULL)

{ j=(HNODE *)malloc(sizeof(HNODE));

j->remainder=box_volume-a[i];

j->head=NULL;

if (box_h==NULL) box_h=box_t=j;

else box_t=boix_t->next=j;

j->next=NULL;

box_count++;

}

else j->remainder-=a[i];

for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);

if (q==NULL)

{ p->link=j->head;

j->head=p;

}

else

{ p->link=NULL;

q->link=p;

}

}

printf(「共使用了%d只箱子」，box_count);

printf(「各箱子裝物品情況如下：」);

for (j=box_h,i=1;j!=NULL;j=j->next,i++)

{ printf(「第%2d只箱子，還剩餘容積%4d，所裝物品有；\n」,I,j->remainder);

for (p=j->head;p!=NULL;p=p->link)

printf(「%4d」,p->vno+1);

printf(「\n」);

}

}

5.分治法

任何一個可以用計算機求解的問題所需的計算時間都與其規模N有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

如果原問題可分割成k個子問題（1<k≤n），且這些子問題都可解，並可利用這些子問題的解求出原問題的解，那麼這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在演算法設計之中，並由此產生許多高效演算法。

分治法所能解決的問題一般具有以下幾個特徵：

（1）該問題的規模縮小到一定的程度就可以容易地解決；

（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；

（3）利用該問題分解出的子問題的解可以合並為該問題的解；

（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

上述的第一條特徵是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特徵是應用分治法的前提，它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；第三條特徵是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮貪心法或動態規劃法。第四條特徵涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。

分治法在每一層遞歸上都有三個步驟：

（1）分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；

（2）解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；

（3）合並：將各個子問題的解合並為原問題的解。

6.動態規劃法

經常會遇到復雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地採用把大問題分解成子問題，並綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規模呈冪級數增加。

為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存於該數組中，這就是動態規劃法所採用的基本方法。以下先用實例說明動態規劃方法的使用。

【問題】 求兩字元序列的最長公共字元子序列

問題描述：字元序列的子序列是指從給定字元序列中隨意地（不一定連續）去掉若干個字元（可能一個也不去掉）後所形成的字元序列。令給定的字元序列X=「x0，x1，…，xm-1」，序列Y=「y0，y1，…，yk-1」是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=「ABCBDAB」，Y=「BCDB」是X的一個子序列。

考慮最長公共子序列問題如何分解成子問題，設A=「a0，a1，…，am-1」，B=「b0，b1，…，bm-1」，並Z=「z0，z1，…，zk-1」為它們的最長公共子序列。不難證明有以下性質：

（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且「z0，z1，…，zk-2」是「a0，a1，…，am-2」和「b0，b1，…，bn-2」的一個最長公共子序列；

（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列；

（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列。

這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找「a0，a1，…，am-2」和「b0，b1，…，bm-2」的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列和找出「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。

代碼如下：

# include <stdio.h>

# include <string.h>

# define N 100

char a[N],b[N],str[N];

int lcs_len(char *a, char *b, int c[ ][ N])

{ int m=strlen(a), n=strlen(b), i,j;

for (i=0;i<=m;i++) c[i][0]=0;

for (i=0;i<=n;i++) c[0][i]=0;

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

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

if (a[i-1]==b[j-1])

c[i][j]=c[i-1][j-1]+1;

else if (c[i-1][j]>=c[i][j-1])

c[i][j]=c[i-1][j];

else

c[i][j]=c[i][j-1];

return c[m][n];

}

char *buile_lcs(char s[ ],char *a, char *b)

{ int k, i=strlen(a), j=strlen(b);

k=lcs_len(a,b,c);

s[k]=』\0』;

while (k>0)

if (c[i][j]==c[i-1][j]) i--;

else if (c[i][j]==c[i][j-1]) j--;

else { s[--k]=a[i-1];

i--; j--;

}

return s;

}

void main()

{ printf (「Enter two string（<%d）!\n」,N);

scanf(「%s%s」,a,b);

printf(「LCS=%s\n」,build_lcs(str,a,b));

}

7.迭代法

迭代法是用於求方程或方程組近似根的一種常用的演算法設計方法。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x)，然後按以下步驟執行：

（1） 選一個方程的近似根，賦給變數x0；

（2） 將x0的值保存於變數x1，然後計算g(x1)，並將結果存於變數x0；

（3） 當x0與x1的差的絕對值還小於指定的精度要求時，重復步驟（2）的計算。

若方程有根，並且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述演算法用C程序的形式表示為：

程序如下：

【演算法】迭代法求方程組的根

{ for (i=0;i<n;i++)

x[i]=初始近似根;

do {

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

y[i] = x[i];

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

x[i] = gi(X);

for (delta=0.0,i=0;i<n;i++)

if (fabs(y[i]-x[i])>delta) delta=fabs(y[i]-x[i])； } while (delta>Epsilon)；

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

printf(「變數x[%d]的近似根是 %f」，I，x[i])；

printf(「\n」)；

} 具體使用迭代法求根時應注意以下兩種可能發生的情況：

（1）如果方程無解，演算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代演算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制；

（2）方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。

8.窮舉搜索法

窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從眾找出那些符合要求的候選解作為問題的解。

【問題】 將A、B、C、D、E、F這六個變數排成如圖所示的三角形，這六個變數分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變數之和相等的全部解。如圖就是一個解。

程序引入變數a、b、c、d、e、f，並讓它們分別順序取1至6的整數，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變數之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變數取盡所有的組合後，程序就可得到全部可能的解。程序如下：

# include <stdio.h>

void main()

{ int a,b,c,d,e,f;

for (a=1;a<=6;a++) {

for (b=1;b<=6;b++) {

if (b==a) continue;

for (c=1;c<=6;c++) {

if (c==a)||(c==b) continue;

for (d=1;d<=6;d++) {

if (d==a)||(d==b)||(d==c) continue;

for (e=1;e<=6;e++) {

if (e==a)||(e==b)||(e==c)||(e==d) continue;

f = 21-(a+b+c+d+e);

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {

printf(「%6d,a);

printf(「%4d%4d」,b,f);

printf(「%2d%4d%4d」,c,d,e);

scanf(「%*c」);

}

}

}

}

}

}}

按窮舉法編寫的程序通常不能適應變化的情況。如問題改成有9個變數排成三角形，每條邊有4個變數的情況，程序的循環重數就要相應改變。

❻ 哪位高手有用C++編寫的解決三維裝箱問題的演算法代碼謝了！

http://www.jos.org.cn/1000-9825/18/2083.pdf
看看這個也許有點啟發

❼ 集裝箱演算法問題 急！！！

我這樣舉例樓主應該會清楚些。

20尺櫃：內容積為5.69米X2.13米X2.18米,配貨毛重一般為17.5噸,體積為24-26立方米.
40尺櫃:內容積為11.8米X2.13米X2.18米,配貨毛重一般為22噸,體積為54立方米.
40尺高櫃:內容積為11.8米X2.13米X2.72米.配貨毛重一般為22噸,體積為68立方米.
45尺高櫃:內容積為:13.58米X2.34米X2.71米,配貨毛重一般為29噸,體積為86立方米.
一個櫃子能裝多少箱的演算法如下:(舉例四十尺櫃)
1. 先算一個產品外箱的體積：(外箱包裝尺寸)
1.2m X 0.45m X 0.66m ＝ 0.3564cbm
2. 算一個40『能裝多少箱， 40『可按57cmb來算
57 / 0.3564 ＝ 160箱

❽ 急需一個裝箱演算法的MATLAB程序！謝謝啦~願出高分！

%裝箱問題FFD演算法實現
%物品的體積
W = [0.125,0.268,0.159,0.168,0.126,0.168,0.249,0.536,0.427,0.179,0.182,0.149,0.156,0.152,0.135,0.161,0.191,0.183,0.174,0.198];
%箱子的編號
V = 1:1:20;
%箱子的體積
U = [1.4,1.3,1.0,1.1];
%箱子的狀態
state = zeros(20,4);

%第一步：將物品體積按照從大到小排序
for i = 1:length(W) - 1
for j = i + 1 :length(W)
if W(i) < W(j)
temp = W(i);
temp_v = V(i);
W(i) = W(j);
V(i) = V(j);
W(j) = temp;
V(j) = temp_v;
end
end
end

%第二步：每次將體積最大的物品放到剩餘體積最小的箱子中
for i = 1:length(W)
%找到剩餘體積最大的箱子
max = 0;%保存剩餘體積最大的體積
max_k = 0;%保存最大體積的箱子的編號
for j = 1:length(U)
if max < U(j)
max = U(j);
max_k = j;
end
end
%將最大的物品放到剩餘體積最大的箱子
if W(i) < U(max_k) & state(V(i),max_k) == 0%如果物品的體積比剩餘的箱子的體積大
state(V(i),max_k) = 1;%狀態發生變化
U(max_k) = U(max_k) - W(i);%箱子的體積變化
else%如果物品的體積比箱子的體積小,則找到下一個剩餘體積最小的箱子
maxx = 0;
maxx_k = 0;
for j = 1:length(U)%找到下一個剩餘空間最小的箱子
if maxx < U(j) & U(j) > U(max_k)
maxx = U(j);
maxx_k = j;
end
end
%將物品放到這個箱子中
if W(i) < U(maxx_k) & state(V(i),maxx_k) == 0
state(V(i),maxx_k) =1;%狀態發生變化
U(maxx_k) = U(maxx_k) - W(i);%箱子的體積變化
else
continue;%否則的話繼續循環下一個物品
end
end
end

❾ 求程序：裝箱問題的近似演算法--NF ( Next Fit ) 演算法。謝謝幫助！

看看這個思路怎麼樣，好像代碼略多。
import java.util.Random;
import java.util.Scanner;
public class FillBox {
private Scanner scann;
private int objNum;
private int boxNum;
private int boxLength;
private Goods[] mGoods;
private Random random;
private Box[] mBox;
public FillBox(){
scann=new Scanner(System.in);
random=new Random();
objNum=getArgsFormConsol("請輸入物品個數objNum：");
boxNum=getArgsFormConsol("請輸箱子個數boxNum：");
boxLength=getArgsFormConsol("請輸箱子長度（單位CM）boxLength：");
//設置物品數組
setGoodsArray(objNum,boxLength);
//設置箱子數組
setBoxAry(boxNum,boxLength);
//開始裝箱子
doFillBox();
//物品的大小情況
showGoodsMessage();
//顯示裝箱情況
showBoxUse();
}
public static void main(String[] args){
new FillBox();
}
public int getArgsFormConsol(String pIntroction){
System.out.print(pIntroction);
int result=scann.nextInt();
System.out.println("***************\n");
return result;
}
public void setGoodsArray(int pNum,int pSize){
mGoods=new Goods[pNum];
for(int i=0;i<pNum;i++){
int goodSize=pSize/4+random.nextInt(pSize/3);
Goods goods=new Goods(i,goodSize);
mGoods[i]=goods;
}
}
public void setBoxAry(int pTolNum,int pSize){
mBox=new Box[pTolNum];
for(int i=0;i<pTolNum;i++){
Box aBox=new Box(i,pSize);
mBox[i]=aBox;
}
}
public void doFillBox(){//開支裝箱子
int aBoxSpaceValue=boxLength;
int currentBoxId=0;
for(int i=0;i<mGoods.length;i++){
if(currentBoxId>=boxNum){
System.out.println("已經沒有足夠的可用的箱子了！");
break;
}
Goods aGod=mGoods[i];
if(mGoods[i].getGoodsLength()<=aBoxSpaceValue){
//裝進這個箱子
mBox[currentBoxId].addGoods(aGod.getGoodsNum());
aBoxSpaceValue-=mGoods[i].getGoodsLength();
}else{
mBox[currentBoxId].setSpaceValue(aBoxSpaceValue);
aBoxSpaceValue=boxLength;//可用長度變長boxLength
currentBoxId++;
i--;//這個貨物裝不下了，換下一個箱子
}
}
}
public void showBoxUse(){
System.out.println("=====================\n下面是裝箱詳細情況：\n====================");
for(int i=0;i<boxNum;i++){
System.out.println("\n"+mBox[i].getShow()+"\n* * * * * * * * * * * * * * *");
}
}
public void showGoodsMessage(){
for(int i=0;i<objNum;i++){
System.out.println("boxID:"+mGoods[i].getGoodsNum()+", box長度："+mGoods[i].getGoodsLength());
}
}
}

public class Goods {
private int goodsNum;
private int goodsLength;
public Goods(){
}
public Goods(int pNum,int pLength){
this.goodsNum=pNum;
this.goodsLength=pLength;
}
public int getGoodsNum() {
return goodsNum;
}
public void setGoodsNum(int goodsNum) {
this.goodsNum = goodsNum;
}
public int getGoodsLength() {
return goodsLength;
}
public void setGoodsLength(int goodsLength) {
this.goodsLength = goodsLength;
}
}

import java.util.Vector;
public class Box {
private int boxNum;
private int boxLength;
private Vector<Integer> containGoodsID;
private int spaceValue;
public Box(){
}
public Box(int pNum,int pLength){
this.boxNum=pNum;
this.boxLength=pLength;
containGoodsID=new Vector<Integer>();
spaceValue=boxLength;
}
public int getBoxNum() {
return boxNum;
}
public void setBoxNum(int boxNum) {
this.boxNum = boxNum;
}
public int getBoxLength() {
return boxLength;
}
public void setBoxLength(int boxLength) {
this.boxLength = boxLength;
}
public void addGoods(Integer pGoodsID){
containGoodsID.add(pGoodsID);
}
public void removieGoods(Integer pGoodsID){
containGoodsID.removeElement(pGoodsID);
}
public int getSpaceValue() {
return spaceValue;
}
public void setSpaceValue(int spaceValue) {
this.spaceValue = spaceValue;
}
public String getShow(){
StringBuffer sb=new StringBuffer("箱子編號："+this.boxNum+" 長度："+this.boxLength+" 可用空間："+spaceValue+"\n本箱子裝的貨物編號：");
for(int i=0;i<containGoodsID.size();i++){
sb.append(containGoodsID.get(i)+", ");
}
return sb.toString();
}
}

可能修飾性的代碼比較多，關鍵邏輯就看doFill（）了

❿ 急需集裝箱裝箱演算法計算公式和方法

1)集裝箱自重系數.即自重與載重之比,計算公式是:
集裝箱自重系數=集裝箱自重/集裝箱載重量
(2)集裝箱比容.指箱內容積與載重量之比,計算公式是:
集裝箱比容(m3/t)=集裝箱內部幾何容積/集裝箱載重量
(3)集裝箱的比面.指集裝箱底面積與載重量之比,計算公式是:
集裝箱比面(m2/t)=集裝箱底部面積/集裝箱載重量
返回