磁带最大利用率问题对于给定的n个程序存放在磁带上的长度，编程计算磁
4星 · 超过85%的资源 需积分: 22 199 浏览量
2009-11-05
23:56:33
上传
评论
收藏 54KB PDF 举报 
算法实现题 4-15 磁带最大利用率问题
问题描述：设有 n 个程序{1，2，……，n}要存放在长度为 L 的磁带上。程序 i 存放在磁带
上的长度是 li,1<=i<=n。
程序存储问题要求确定这 n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽
可能多的程序。在保证存储最多程序的前提下还要求磁带的利用率达到最大。
算法设计：对于给定的 n 个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数和
占用磁带的长度。
数据输入：由文件 input.txt 给出输入数据。第 1 行是两个正整数，分别表示文件个数 n 和磁
带的长度 L。接下来的 1 行中，有 n 个正整数，表示程序存放在磁带上的长度。
结果输出：将计算的最多可以存储的程序数和占用磁带的长度及存放在磁带上的每个程序的
长度输出到文件 output.txt。第 1 行输出最多可以存储的程序数和占用磁带的长度；第 2 行
输出存放在磁带上的每个程序的长度。
解答：本题可采用回溯法解决。
001 #include <iostream>
002 #include <fstream>
003 using namespace std;
004
005
006 template<class Type>
007 class Loading{
008 friend Type MaxLoading(Type [],Type,int,int [],int &);
009 private:
010 void Backtrack(int i);
011 int n,
012 * x, //当前解
013 *bestx, //当前最优解
014 r,
015 count; //当前存储程序数
016
017 Type* l,
018 c, //磁带长度
019 cl, //当前占用磁带长度
020 bestl; //最大利用磁带长度
021 public:
022 int maxcount; //最大存储程序数
023
024 };
025
026 template<class Type>
027 void Loading<Type>::Backtrack(int i)
资源评论
van_lucretia2013-08-02还可以吧，，不过还需要改进呢
luoyufen2013-01-02虽然不是我要的算法，但是还是要感谢分享- belindee2012-12-26虽然不是我要的算法，但是还是要感谢分享
