【贪心法】程序存储问题

简介: 【贪心法】程序存储问题

 题目描述:

设有n个程序{1,2,…, n }要存放在长度为L 的磁带上。程序i存放在磁带上的长度是li,1≤i≤n 。程序存储问题要求确定这n个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序。

编程任务:

  对于给定的n 个程序存放在磁带上的长度,编程计算磁带上最多可以存储的程序数。

数据输入:

  (由文件input.txt 给出输入数据。)第一行是2个正整数,分别表示文件个数n 和磁带的长度L。接下来的1行中,有n个正整数,表示程序存放在磁带上的长度。

结果输出:

  将编程计算出的最多可以存储的程序数输出(到文件output.txt)

输入文件示例输出文件示例

input.txt                        output.txt

6 50                             5

2 3 13 8 80 20

注:若题目要求含上述括号中橙色字体,即将代码第11、12行注释解除,让其执行即可。

代码如下:

#include <iostream>
#include <algorithm>//sort()头文件 
#include <fstream>//文件读写操作头文件 
using namespace std;
#define N 10000
bool cmp(int x,int y){
  return x<y;
}
int main(){
  //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
  int n,L; cin>>n>>L;//输入文件个数,磁带长度
  int Long[N];
  for(int i=0;i<n;i++){
    cin>>Long[i];
  } 
  sort(Long,Long+n,cmp);//以升序排列 
  int flag=0;//记录存储第flag个程序,flag从0开始(数组存储从0开始) 
  int LongSum=0;//记录存储的程序长度和 
  int Num=0;//记录存储的程序个数 
  while(flag<n){
    LongSum=LongSum+Long[flag];//求和 
    if(LongSum>L) break;//超出磁带长度,跳出循环 
    else Num++;
    flag++; 
  }
  cout<<Num<<endl;
  return 0;
}

image.gif


目录
相关文章
|
27天前
|
存储 算法
深入了解动态规划算法
深入了解动态规划算法
47 1
|
6月前
|
算法 Java C++
非启发式算法——二分、三分搜索算法
非启发式算法——二分、三分搜索算法
206 0
|
存储 人工智能 自然语言处理
动态规划算法总结
动态规划算法总结
|
存储 算法 搜索推荐
动态规划算法
动态规划算法是一种常用的优化问题求解方法,主要用于解决具有重叠子问题和最优子结构性质的问题。动态规划算法的基本思想是将原问题拆分成若干个子问题,通过求解子问题的最优解来求解原问题的最优解。动态规划算法通常包含以下三个步骤:
123 2
|
机器学习/深度学习 自然语言处理
动态规划算法(一)
动态规划算法
90 0
|
机器学习/深度学习 人工智能 JavaScript
动态规划算法(二)
动态规划算法
63 0
|
存储 算法
【回溯算法篇】组合问题(上)
【回溯算法篇】组合问题(上)
【回溯算法篇】组合问题(上)
【回溯算法篇】组合问题(下)
【回溯算法篇】组合问题(下)
【回溯算法篇】组合问题(下)
|
缓存 算法 网络协议
贪心法
贪心法是把一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个扩展,直到获得问题的完整解。贪心法的典型应用是求解最优化问题,而且对许多问题都能得到整体最优解,即使不能得到整体最优解,通常也是最优解的很好近似。
|
存储 缓存 移动开发
动态规划法
动态规划是在20世纪50年代由美国数学家贝尔曼为研究最优控制问题而提出的,当该方法在应用数学中的价值被大家认同以后,在计算机学界,动态规划法成为一种通用的算法设计技术用来求解多阶段决策最优化问题。