算法第四章上机实验报告
2021/11/12 22:14:43
本文主要是介绍算法第四章上机实验报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、实验题目 4-1 程序存储问题 (40 分)设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li,1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案, 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度,计算磁带上最多可以存储的程序数。
输入格式:
第一行是2 个正整数,分别表示文件个数n和磁带的长度L。接下来的1行中,有n个正整数,表示程序存放在磁带上的长度。
输出格式:
输出最多可以存储的程序数。
输入样例:
在这里给出一组输入。例如:
6 50
2 3 13 8 80 20
输出样例:
在这里给出相应的输出。例如:
5
二、算法描述
本题要求存储的程序数最多,则我们的贪心选择是尽可能的找出最小长度的程序以保证磁带上的程序数最多。首先用排序将给出的长度进行由小到大的排序,接着从小到大一直挑选直到超出磁带长度为止(要判断,有可能出现刚好的情况),最后输出程序的数量即可
三、我的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,L;
cin>>n>>L;
int a[1000];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int count=0;
int sum=0;
for(int i=0;i<n;i++){
sum+=a[i];
if(sum<=L)
count++;
else break;
}
cout<<count<<endl;
return 0;
}
四、复杂度
用了一次sort,时间复杂度为o(nlogn)
空间复杂度为o(n)
五、心得体会
贪心算法是通过一系列的选择来得到问题的解,每一个选择都是当前状态下局部的最好选择。它能大大的简化代码以及程序运行的时间复杂度,但有时候十分难想到它的贪心选择和最优子结构,导致一些问题无法下手,只能通过多观摩学习优秀代码来提高自己对它的理解。
这篇关于算法第四章上机实验报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现