算法设计与分析 - 磁带存储程序 - 贪心算法（java实现）

左手的ㄟ右手 2022-02-19 18:47 396阅读 0赞

### 题目描述： ###

设有n个程序\{1,2，...,n\}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1<=i<=n.  
程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下，  
要求磁带的利用率最大。  
编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占用磁带的长度。  
提示：利用贪心策略：最短程序优先。求得最多可以存储的程序个数m后，再求最大利用率。问题转化为第5章中的装载问题，但m已知。  
 输入描述  
第一行是2个正整数，分别表示文件个数n和磁带长度L。第二行中，有n个正整数，表示程序存放在磁带上的长度。  
 输出描述  
第一行输出最多可以存储的程序数和占用磁带的长度；第二行输出存放在磁带上的每个程序的长度。  
 输入样例

9 50
    2 3 13 8 80 20 21 22 23

输出样例

5 49
    2 3 13 8 23

###    java代码如下： ###

import java.util.Arrays;
    import java.util.Scanner;
    
    
    public class Main {
    
    	public static void main(String[] args){
    		
    		
    		int []a = new int[1001];
    		int n,c, max= 0;
    		int num = 0;
    		
    			Scanner input = new Scanner(System.in);
    			n = input.nextInt();
    			c = input.nextInt();
    			
    		for(int i=1;i<=n;i++)
    		{
    			
    			a[i] = input.nextInt();
    			
    			//System.out.println(a[i]);	
    
    		}
    		//输入数据，第一行是2个正整数分别是文件个数n和磁带长度L，接下来的i行中，有n个整数，表示程序存储所需的磁带长度
    		
    		//对输入的程序按长度进行排序
    	for(int i =1;i <= n;i++) {
    		for(int j = 1; j<= n-i;j++) {
    			if(a[j] > a[j+1]) {
    				int temp = a[j];
    				a[j] = a[j+1];
    				a[j+1] = temp;
    			}
    		}
    	}
    		
    	
    		for(int i = 1;i <= n;i ++){
    			System.out.println(a[i]+ " ");
    			c -= a[i ];
    			if(c >= 0)
    				num++;
    			
    			else break;
    			}
    		
    		System.out.println(num);
    		}
    	
    	
    
    }

![20190416224232713.png][]

参考文章：

[https://blog.csdn.net/u010862301/article/details/40480657][https_blog.csdn.net_u010862301_article_details_40480657]

[https://blog.csdn.net/bensonrachel/article/details/78595809][https_blog.csdn.net_bensonrachel_article_details_78595809]

[20190416224232713.png]: /images/20220219/07e2a9e11e32434ca30e4c8684336413.png
[https_blog.csdn.net_u010862301_article_details_40480657]: https://blog.csdn.net/u010862301/article/details/40480657
[https_blog.csdn.net_bensonrachel_article_details_78595809]: https://blog.csdn.net/bensonrachel/article/details/78595809