?? 裝載問題跌代回溯.cpp
字號:
//? 裝載問題跌代回溯
#include <iostream.h>
const int n=5;
void main()
{
int C=65, W[n]={10,22,40,15,31};
int j=0; //已裝上輪船的集裝箱數(shù)
int x[n]={0}; //裝上輪船的集裝箱號
int m[n]={0};
cout<<"\n輪船承載量:"<<C;
cout<<"\n\n集裝箱重量:";
for (int i=0; i<n; ++i) cout<<W[i]<<" ";
int n0=n;
int min1=C; //最小剩余量
while (n0>0)
{
while (i>0)
{
if (C>=W[i-1])
{
x[j++]=i;
C-=W[i-1];
}
i--;
}
if (j==n && C>0)
{
cout<<"\n\n所有集裝箱都裝上了輪船。";
break;
}
if (C<min1)
{
min1=C;
for (int k=0; k<j; ++k) m[k]=W[x[k]-1];
for (k=j; k<n; ++k) m[k]=0;
}
if (C==0)
{
cout<<"\n\n裝載解向量:";
i=n;
while (x[--i]==0) ;
for (int k=1; k<=n; k++)
if (k==x[i])
{
cout<<" 1 ";
i--;
}
else cout<<" 0 ";
cout<<"\n\n恰好裝滿輪船:";
for (i=j-1; i>=0; --i) cout<<W[x[i]-1]<<" ";
break;
}
j--;
i=x[j];
C+=W[i-1];
if (i==n0)
{
i=n0-1;
n0=i;
}
else i--;
}
if (j==0)
{
cout<<"\n\n最優(yōu)裝載方案:";
i=n;
while (m[--i]==0);
while (i>=0)
{
cout<<m[i]<<" ";
j+=m[i];
i--;
}
cout<<"\n\n已經(jīng)裝載重量:"<<j;
}
cout<<"\n\n";
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -