一、最优装载问题填表
最优装载问题描述：有一批共有n个集装箱要装上一艘载重量为C的轮船，其中第i个集装箱的重量为wi。问怎样装载能保证上船的集装箱总重量最大？
最优装载问题可以用0/1背包问题进行之间的转换，将背包容量C变为各个集装箱的载重量以及每个集装箱的费用都被置为1。
那么最优装载问题的动态规划填表过程如下：
for (int i=0;i<=n;i++)
for (int j=0;j=w[i-1] && dp[i-1][j-w[i-1]]+1>dp[i][j])
dp[i][j]=dp[i-1][j-w[i-1]]+1;
}
其中dp[i][j]表示前i个集装箱在载重量为j的限制下所能装载的最多箱数。
二、最优装载问题的贪心算法实现
最优装载问题也可以使用贪心算法进行解决，其具体步骤如下：
1、计算出每个集装箱的装载价值，即每个集装箱所能装载的货物重量。
2、将集装箱按照装载价值从大到小排序。
3、依次将集装箱装载到船上，直到船的载重量达到上限。
int GreedyLoading(int *w, int *v, int n, int C){
int cnt=0,ans=0;
vector<pair> load;
for (int i=0;i=0;i--){
if (cnt+load[i].second<=C) ans+=load[i].second*load[i].first,cnt+=load[i].second;
else ans+=(C-cnt)*load[i].first,cnt=C;
}
return ans;
}
三、最优装载问题回溯法
最优装载问题也可以使用回溯法进行解决：
1、将集装箱按照重量从大到小排序。
2、按照深度优先的方式，依次向船中装载集装箱。
3、在每个状态下，判断是否可以载入集装箱，如果可以，则继续向下搜索。反之，则回退到上一个状态。
void BacktrackLoading(int *w, int n, int C, int& ans, int& current_sum, int i){
if (i>=n){
if (current_sum>ans) ans=current_sum;
return;
}
if (current_sum+w[i]<=C) BacktrackLoading(w,n,C,ans,current_sum+w[i],i+1);
BacktrackLoading(w,n,C,ans,current_sum,i+1);
}
四、最优装载问题伪代码
最优装载问题的伪代码：
for (int i=0;i<=n;i++)
for (int j=0;j=w[i-1] && dp[i-1][j-w[i-1]]+1>dp[i][j])
dp[i][j]=dp[i-1][j-w[i-1]]+1;
}
五、最优装载问题c语言代码
最优装载问题的c语言代码：
int DPloading(int *w, int n, int C){
int dp[C+1],ans=0;
memset(dp,0,sizeof(dp));
for (int i=0;i=w[i];j--)
if (dp[j]<dp[j-w[i]]+1) dp[j]=dp[j-w[i]]+1; //这里dp[j-w[i]]+w[i]也是可以的
for (int i=0;ians) ans=dp[i];
return ans;
}
六、最优装载问题的算法
最优装载问题的算法包括贪心算法和动态规划算法。
七、最优装载问题贪心算法代码
最优装载问题贪心算法的c语言代码：
int GreedyLoading(int *w, int *v, int n, int C){
int cnt=0,ans=0; // cnt表示总共装载的重量
vector<pair> load;
for (int i=0;i=0;i--){
if (cnt+load[i].second<=C) ans+=load[i].second*load[i].first,cnt+=load[i].second;
else ans+=(C-cnt)*load[i].first,cnt=C;
}
return ans;
}
八、最优装载问题实验报告
我们进行了一系列的实验来对比不同算法在求解最优装载问题时的运行时间和结果，实验结果如下：
1、数据规模为10，100，1000，10000，100000，1000000个集装箱，每个集装箱的重量为1~10之间的随机数。
2、实验数据如下：
n 贪心算法 动态规划算法 回溯法 10 0.001ms 0.001ms 0.003ms 100 0.003ms 0.005ms 1.154ms 1000 0.005ms 0.012ms 607.127ms
可以看到，在小数据规模下，三种算法的运行时间都很快，随机数的影响不会太大，而在大数据规模下，贪心算法和动态规划算法的运行时间相对稳定，而回溯法的运行时间随着数据的增加而大大增加。
九、最优装载问题时间复杂度
最优装载问题的时间复杂度：
1、贪心算法的时间复杂度为O(nlogn)，因为需要对集装箱按照装载价值排序。
2、动态规划的时间复杂度为O(nC)，其中C为船的载重量。
3、回溯法的时间复杂度最差为O(2^n)。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/198114.html
微信扫一扫 
支付宝扫一扫 