广州怎么做网站/环球网今日疫情消息

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。

//Sort函数的目的是将集装箱的序号按照集装箱重量从小到大排序
void Sort(Type w[],int t[],int n)
{int temp;for(int i=1;i<=n;i++)t[i]=i;//初始时默认集装箱序号为升序for(int i=1;i<=n;i++)for(int j=1;j<=n-i;j++){if(w[j]>w[j+1])//如果前者比后者重交换其序号{temp=t[j];t[j]=t[j+1];t[j+1]=temp;}}
}
template<class Type>
//c为轮船载重量，n为集装箱数目
//w[]表示集装箱的重量
//x[]表示集装箱是否装入轮船，x[i]=0或1
void Loading(int x[],Type w[],Type c,int n)
{int *t = new int[n+1];Sort(w,t,n);//t[1]=3,t[2]=2,t[3]=1,t[4]=4,t[5]=5for(int i=1;i<=n;i++)x[i]=0;for(int i=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c=c-w[t[i]];}
}

完整代码

#include <iostream>
using namespace std;
typedef  float Type;
//Sort函数的目的是将集装箱的序号按照集装箱重量从小到大排序
void Sort(Type w[],int t[],int n)
{int temp;for(int i=1;i<=n;i++)t[i]=i;//初始时默认集装箱序号为升序for(int i=1;i<=n;i++)for(int j=1;j<=n-i;j++){if(w[j]>w[j+1])//如果前者比后者重交换其序号{temp=t[j];t[j]=t[j+1];t[j+1]=temp;}}
}
//c为轮船载重量，n为集装箱数目
//w[]表示集装箱的重量
//x[]表示集装箱是否装入轮船，x[i]=0或1
void Loading(int x[],Type w[],Type c,int n)
{int *t = new int[n+1];Sort(w,t,n);//t[1]=3,t[2]=2,t[3]=1,t[4]=4,t[5]=5for(int i=1;i<=n;i++)x[i]=0;for(int i=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c=c-w[t[i]];}
}
int main()
{int n;Type c;cin>>n>>c;Type w[n+1];for(int i=1;i<=n;i++)cin>>w[i];int x[n+1];Loading(x,w,c,n);for(int i=1;i<=n;i++)cout<<x[i]<<" ";return 0;
}

贪心选择性质

可以证明最优装载问题具有贪心选择性质。

最优子结构性质

最优装载问题具有最优子结构性质。
由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。
算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。