演算法裝載問題
⑴ 裝載問題的貪心選擇性質如何證明
設箱子重量從小到大（x1,x2,...,xn），若集合A是最優裝載問題的一個最優解。A中第一個箱子為k。若k=1，A就是一個滿足貪心性質的最優解。假如當k>1，令B=A-{k}+{1},因為Wk>=W1,則B中的總重量小於等於A中的總重量，A是最優解，則B也是最優解，而B是選擇以箱子1為開始的最優解。可知總存在以貪心選擇開始的最優解。
⑵ 演算法的相關
經典的演算法有很多，如歐幾里德演算法，割圓術，秦九韶演算法。
隨著計算機的發展，演算法在計算機方面已有廣泛的發展及應用，如用隨機森林演算法，來進行頭部姿勢的估計，用遺傳演算法來解決彈葯裝載問題，信息加密演算法在網路傳輸中的應用，並行演算法在數據挖掘中的應用等。
⑶ 裝載問題 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]算什麼？你的方程含義是在不超過最大容量的情況下，最多裝的重量為多少。顯然不對。
⑷ 我也想要演算法設計與分析的習題答案，只要回溯法的裝載問題改進程序那兩個，幫個忙啊
這個應該不錯
var a:array[0..11] of integer;
n,k,t:integer;
procere p(k:integer);
var i,j:integer;
g:boolean;
begin
if k>n then begin
for i:=1 to n-1 do
write(a[i],' ');
writeln(a[n]);
t:=t+1;
end
else begin
for i:=1 to n do begin
g:=true;
for j:=1 to k-1 do
if (i=a[j]) or (abs(i-a[j])=abs(k-j)) then g:=false;
if g then
begin
a[k]:=i;
p(k+1);
end;
end;
end;
end;
begin
readln(n);
t:=0;
k:=1;
p(k);
if t=0 then writeln('no solute!');
if t>0 then writeln(t);
end.
⑸ 演算法 C++ 裝載問題 分支定界
不會，非最優解不會包含最優解，如果包含了，這就是一個更優的解。
⑹ 跪求演算法!!!!!!!!!!!!
最有裝載問題?
網路.
⑺ 關於裝載問題的C++
將MaxLoading(*w,c,n,*bestx); 修改為：
MaxLoading(w,c,n,bestx);
就可以了
另外，你這個程序估計你敲錯的太多了
我修改後，可以編譯過，也許有其他邏輯錯誤：
#include <conio.h>
#include <iomanip.h>
#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
template<class Type>
class Loading
{
friend Type MaxLoading(Type[],Type,int,int[]);
private:
void Backtrack(int i);
int n,*x,*bestx;
Type*w,c,cw,bestw,r;
};
template<class Type>
void Loading<Type>::Backtrack(int i)
{
if(i>n-1)
{
if(cw>bestw)
{
for(int j=0;j<=n-1;j++)
{
bestx[j]=x[j];
bestw=cw;
}
return;
}
r-=w[i];
if(cw+w[i]<=c)
{
x[i]=1;
cw+=w[i];
Backtrack(i+1);
cw-=w[i];
}
if(cw+r>bestw)
{
x[i]=0;
Backtrack(i+1);
}
r+=w[i];
}
}
template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
Loading<Type>X;
X.x=new int[n+1];
X.w=w;
X.c=c;
X.n=n;
X.bestx=bestx;
X.bestw=0;
X.cw=0;
X.r=0;
for(int i=1;i<=n;i++)
X.r+=w[i];
X.Backtrack(1);
delete[]X.x;
return X.bestw;
}
void main()
{
int c,n,*w,*bestx,i;
cout<<"輸入輪船的重量:"<<endl;
cin>>c;
cout<<endl;
cout<<"輸入貨箱個數:";
cin>>n;
cout<<endl;
w=new int[n];
bestx=new int[n];
cout<<"請輸入"<<n<<"貨箱重量:";
for(i=0;i<n;i++)
{
cin>>*(w+i);
}
for(i=0;i<n;i++)
{
*(bestx+i)=0;
}
MaxLoading(w,c,n,bestx);
}
⑻ 貪心演算法的最優裝載問題
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（;;）是冒號，非逗號
⑼ C語言關於裝載問題（背包問題）的一個程序 我寫的程序輸出不滿足題意 但我檢查不出來錯誤 希望大神解決
想法:是先讓c1船盡量裝貨物是可以的，但是演算法應該不對，可以用下面的演算法
// 前k個數中去任意個數，且這些數之和為s的取法是否存在
int main()
{
int n, i, k1, k2, s, u;
cin >> n;
for (i=1; i<=2*n; i++)
cin >> A[i];
int sum = 0;
for (i=1; i<=2*n; i++)
sum += A[i];
memset(dp,0,sizeof(dp));
dp[0][0]=true;
// 外階段k1表示第k1個數，內階段k2表示選取數的個數
for (k1=1; k1<=2*n; k1++) // 外階段k1
{
for (k2=k1; k2>=1; k2--) // 內階段k2
for (s=1; s<=sum/2; s++) // 狀態s
{
//dp[k1][s] = dp[k1-1][s];
// 有兩個決策包含或不包含元素k1
if (s>=A[k1] && dp[k2-1][s-A[k1]])
dp[k2][s] = true;
}
}
// 之前的dp[k][s]表示從前k個數中取任意k個數，經過下面的步驟後
// 即表示從前k個數中取任意個數
for (k1=2; k1<=2*n; k1++)
for (s=1; s<=sum/2; s++)
if (dp[k1-1][s]) dp[k1][s]=true;
// 確定最接近的給定值sum/2的和
for (s=sum/2; s>=1 && !dp[2*n][s]; s--);
}
⑽ 如何證明最優裝載問題具有貪心選擇性質
設某種貨幣系統為(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達到最小，仍為同 型的最優問題。