Java教程

算法第四章上机实践报告

本文主要是介绍算法第四章上机实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 题目:程序存储问题

设有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
结尾无空行
2. 算法

贪心策略:在有限的磁盘上存放尽可能多的程序,就要求选择的程序尽可能小。对程序长度进行非降序排序,总是从可选程序中选择最小的试放入磁盘。

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n, l;
    cin >> n >> l; // n:程序数  l:磁带长度
    int a[n];
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int sum = 0 ; // 当前放入磁带的程序的总长度
    int count = 0;  // count:用来计数
    for (int i = 1; i <= n; i ++){
        sum += a[i];
	if (sum <= l){
	    count++;
	}
	}
	cout << count;
	return 0;
}

1.3 证明满足贪心选择性质

设集合A是程序存储问题的一个最优解,A中最先放入磁带的是程序k。若k = 1,则最优解包含程序1,即A是一个以贪心选择开始的最优解;若k>1(最优解不包含程序1),令B = A – {k}∪{1},因为程序 1 的长度小于程序 k 的长度,且 A中的程序个数与B相同,故B也是一个最优解,而B包含程序1,故总存在以贪心选择开始的最优存储方案。

1.4 时间和空间复杂度分析

时间复杂度:程序进行了一次快排(O(nlogn))和循环(O(n)),故时间复杂度为O(nlogn)。

空间复杂度:程序用了一个一维数组(a[n])用于存放每个程序的大小,故空间复杂度为O(n)。

2. 对贪心算法的理解体会

在贪心算法中,仅在当前状态下做出最好选择。用贪心算法求解题目时,首先提出贪心策略,然后证明策略正确。解题的关键在于贪心策略的选择。但贪心算法并不是对所有问题都能得到整体最优解,因此需要判断问题是否具有贪心选择性质。

这篇关于算法第四章上机实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!