免费建立自己的网站空间,义乌网络推广公司,湖州网站设计公司,网页制作教程免费下载算法背景 在北美洲东南部#xff0c;有一片神秘的海域#xff0c;那里碧海蓝天、阳光 明媚#xff0c;这正是传说中海盗最活跃的加勒比海#xff08;Caribbean Sea#xff09;。 有一天#xff0c;海盗们截获了一艘装满各种各样古董的货船#xff0c;每一 件古董都价值连…算法背景 在北美洲东南部有一片神秘的海域那里碧海蓝天、阳光 明媚这正是传说中海盗最活跃的加勒比海Caribbean Sea。 有一天海盗们截获了一艘装满各种各样古董的货船每一 件古董都价值连城一旦打碎就失去了它的价值。虽然海盗船足 够大但载重量为C每件古董的重量为wi海盗们该如何把尽 可能多数量的宝贝装上海盗船呢
问题分析 贪心策略 本题要求物品不可分割要求装载的物品的数量尽可能多而船的载重量 是固定的那么优先把重量小的物品放进去在载重量固定的情况下装的物 品最多。 贪心选择策略重量最小者先装 从局部最优达到全局最优从而产生最优装载问题的最优解。 算法设计 算法设计 1当载重量为定值c时wi越小时可装载的古董数量n越大。只要依次选 择最小重量古董直到不能再装为止。 2把n个古董的重量从小到大非递减排序然后根据贪心策略尽可能多 地选出前i个古董直到不能继续装为止此时达到最优。 完美图解 表2-1 古董重量清单 1因为贪心策略是每次选择重量最小的古董装入海盗船因此可以按照古董重 量非递减排序排序后如表2-2所示。
表2-2 按重量排序后古董清单 2按照贪心策略每次选择重量最小的古董放入tmp 代表古董的重量ans 代表已装裁的古董个数。 算法的伪代码 实战演练
#includeiostream
#includealgorithm
using namespace std;
const int maxn 1e6 10;
int q[maxn];//宝物重量的数组
int n,max1;//n-宝物的数量max1-串只所能载的最大重量
int main(){cinnmax1;int sum1 0;int count 0;//船能装载货物的数量 for(int i 0;i n - 1;i ){cinq[i];}sort(q,qn);for(int i 0;i n - 1;i ){sum1 q[i];count ;if(sum1 max1){sum1 - q[i];break;}}coutsum1endl;coutcount - 1endl;return 0;}
