最優裝載問題課程設計

Ⅰ 裝載問題 PASCAL 高手來幫幫

^我看的沒錯的話，抄你這個程序用的襲搜索，時間復雜度為（2^n),n只要到16你的程序准超時。所以搜索不是這個題的最優演算法。這個題的最優演算法是DP。很明顯是個背包問題，我直接給你DP方程,你用2個for循環OK。
f[i,j]=max(f[i-1,j],f[i-1,j-w[i]]+1);
程序再怎麼剪枝也沒用啊，我如果n=31，就有2*10^9中可能，搜索肯定過不了，這個題就是動態規劃，你從網上查一下DD牛的背包九講。這個題屬於第一個類型。
好吧……我錯了……我不是很擅長剪枝。
價值怎麼不是1？他要求的是最大的集裝箱數目。那每裝上一個，自然價值+1，你加個w[i]算什麼？你的方程含義是在不超過最大容量的情況下，最多裝的重量為多少。顯然不對。

Ⅱ 將最優裝載問題的貪心演算法推廣到2艘船的情形，貪心演算法仍能產生最優解嗎

貪心演算法不能產生最優解。

兩艘船的裝載問題，是先裝完第一艘，再裝第版二艘，所以權就必須把第一艘盡可能的裝滿，才能使總的裝載量更多。

對於一個具體問題，要確定它是否具有貪心選擇的性質，必須證明每一步所作的貪心選擇最終能得到問題的最優解，通常可以首先證明問題的一個整體最優解，是從貪心選擇開始的，而且作了貪心選擇後，原問題簡化為一個規模更小的類似子問題。

(2)最優裝載問題課程設計擴展閱讀：

兩艘船的裝載問題需要用的是回溯法，有了問題的解空間後，還需要將解空間有效地組織起來，使得回溯法能方便地搜索整個解空間，通常將解空間組織成樹或圖的形式。

如果在當前的擴展結點處不能再向縱深方向移動，則當前的擴展結點就成為死結點。此時應往回移動(回溯)至最近的一個活結點處，並使其成為當前的擴展結點。回溯法以上述工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結點時為止。

此外，貪心演算法的每一次操作都對結果產生直接影響，而動態規劃則不是。貪心演算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。

Ⅲ 急求java實現最優裝載問題。。。。。。。。。。。

是不是先將集裝箱按照重量排個序，然後先裝最輕的，依次裝上去，當第i+1個裝上去超過c時，就裝i個。

Ⅳ 最優裝載問題 c++

這個可以用貪心法去計算得出最優解，或者接近最優解，我有這方面的例子，要的話，跟我說一下唄

Ⅳ 如何證明最優裝載問題具有貪心選擇性質

設箱子重量從小到大（x1,x2,...,xn），若集合a是最優裝載問題的一個最優解。a中第一個箱子為k。若k=1，a就是一個滿足貪心性質的最優解。假如當k>1，令b=a-{k}+{1},因為wk>=w1,則b中的總重量小於等於a中的總重量，a是最優解，則b也是最優解，而b是選擇以箱子1為開始的最優解。可知總存在以貪心選擇開始的最優解。

Ⅵ 貪心演算法的最優裝載問題

void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)

1.void loading(int W[],int X[],int c,int n)
2.沒有定來義自i;
3.for（;;）是冒號，非逗號

Ⅶ 如何證明最優裝載問題具有貪心選擇性質

設某種貨幣系統為(1,5,10,25)四種幣值(單位:元)，要用最少的幣數找出 n元錢，
問:能否用貪心演算法進行求解，並證明。(不要求寫演算法) 參考解答:貪心性質(最大面額優先選最多)證明:
對 n<=25的情況，易由窮舉得證。
當 n>25時，設 n=1*a1+5*a2+10*a3+25*a4
為了使 a1+a2+a3+a4最小，易知:
a1<5，若 a1>=5，可將 5個 1元兌換為 1個 5元，幣數減少。
a2<2，若 a2>=2，可將 2個 5元兌換為 1個 10元，幣數減少。
當 a2=0時，a3<3，若 a3>=3，可將 3個 10元兌換為 1個 5元和 1個 25元，幣數減 少。
當 a2>0時，a3<2，若 a2>=2，可將 1個 5元和 2個 10元兌換為 1個 25元，幣數減 少。
即，為了使 a1+a2+a3+a4最小，所使用的 1、5、10元幣的幣數的上限為: a1=4,a2=0,a3=2或 a1=4,a2=1,a3=1
則所使用的 1、5、10元幣的幣值上限為:
4*1+0*5+2*10=24或 4*1+1*5+1*10=19
均不超過 25，因此，為了使 a1+a2+a3+a4最小，應使 a4達到最大。貪心選擇性質得 證。
最優子結構性質證明:
當 a4的值確定後，為了使 a1+a2+a3+a4達到最小，須使 a1+a2+a3達到最小，仍為同 型的最優問題。

Ⅷ 裝載問題的貪心選擇性質如何證明

設箱子重量從小到大（x1,x2,...,xn），若集合A是最優裝載問題的一個最優解。A中第一個箱子為k。若k=1，A就是一個滿足貪心性質的最優解。假如當k>1，令B=A-{k}+{1},因為Wk>=W1,則B中的總重量小於等於A中的總重量，A是最優解，則B也是最優解，而B是選擇以箱子1為開始的最優解。可知總存在以貪心選擇開始的最優解。

Ⅸ 最優裝載問題求解

動態規劃經典問題，網上搜0-1背包