您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

作业 10

1.问题
设船的载重量为C,每个集装箱的重量wi<=C,x i = 0或1,xi=1表示第i个集装箱可以装上船,否则x i = 0
则问题可以描述为:(第一行左为目标函数,右为约束条件)

2.解析
贪心法:每次都选择最轻的,然后再从剩下的n-1件物品中选择最轻的。把n件物品按照重量,从小到大排序,轻者先装,直到再装任何集装箱使得轮船载重量超过C停止。

3.设计
输入集装箱个数n
输入轮船载重量C
输入各个集装箱重量m[i]
qsort(m,n,sizeof(int),cmp)
for(i=0;i<n;i++){
C-=m[i];
if(C>0)
printf("%d ",m[i]) ;
else
break;
}

4.分析
W(n)= nlogn​

5.源码
https://github.com/kukukiki11/-/blob/main/%E8%A3%85%E8%BD%BD%E9%97%AE%E9%A2%98.cpp


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进