ACM-Maximum Tape Utilization Ratio
2024-09-03 20:27:38
题目描述：Maximum Tape Utilization Ratio
Tags: 贪婪策略
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li ，1 < = i < = n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下还要求磁带的利用率达到最大。 对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占用磁带的长度。
输入
第一行是2 个正整数，分别表示文件个数n <=600和磁带的长度L<=6000。接下来的1 行中，有n个正整数，表示程序存放在磁带上的长度。
输出
第1 行输出最多可以存储的程序数和占用磁带的长度；第2行输出存放在磁带上的每个程序的长度。
样例输入
9 50
2 3 13 8 80 20 21 22 23
样例输出
5 49
2 3 13 8 23 思路：先排序，最大可能存储程序的个数，然后DFS找到最优解。
备注：直接上来就DFS，一般般都会超时，用贪心策略才能A。
// Maximum Tape Utilization Ratio.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h" //超时！！！！！
//#include <stdio.h>
//#include <string.h>
//#include <algorithm>
//#include <iostream>
//using namespace std;
//
//#define MAX 605
//int n, len, L[MAX], maxL = 0 /*存储的最大长度*/, maxS = 0/*存储的最多程序数目*/, vis[MAX], path[MAX];
//
//int cmp(int a, int b)
//{
// return a < b;
//}
//
////DFS,index为当前处理的物品编号
////sumS和sumL分别为当前总程序数和当前总长度
//void DFS(int index, int sumS, int sumL)
//{
// if (sumL > len) return;
// if (index >= n)
// { //已经完成了对n件物品的选择（死胡同）
// if (sumS > maxS || (sumS == maxS && maxL < sumL))
// {
// maxS = sumS;
// maxL = sumL;
// memcpy(path, vis, sizeof(vis));
// }
// return;
// }
// //岔道口
// vis[index]= 0 ; DFS(index + 1, sumS, sumL);//不选择第index件物品
// if ((len - sumL) >= L[index])
// vis[index] = 1; DFS(index + 1, sumS + 1, sumL + L[index]);//选择第index件物品
//}
//
//int main()
//{
// scanf("%d %d", &n, &len);
// for (int i = 0; i < n; i++) scanf("%d", &L[i]);
//
// memset(vis, 0, sizeof(vis));
// memset(path, 0, sizeof(path));
//
// sort(L, L + n,cmp);
// DFS(0, 0, 0);
//
//
// //搜索背包路径
// int ans = 0, num = 0, res[MAX];
// for (int i = 0, flag = 0; i < n; i++)
// {
// if (path[i])
// {
// ans += L[i];
// res[num++] = L[i];
// }
// }
// printf("%d %d\n", num,ans);
// for (int i = 0; i < num;i++)
// if (i != n - 1) printf("%d ", res[i]);
// else printf("%d\n", res[i]);
//
// return 0;
//} //超时解决方法：直接保存最优路径
//#include <stdio.h>
//#include <algorithm>
//#include <iostream>
//using namespace std;
//
//#define MAX 605
//int n, len, L[MAX];
//
//struct Path
//{
// int num;
// int len;
// int p[MAX];
//}maxPath;
//
//int cmp(int a, int b)
//{
// return a < b;
//}
//
////DFS,index为当前处理的物品编号
//void DFS(int index,Path cur)
//{
// if (cur.len > len) return;//长度超了
// if ((cur.num + len - index) < maxPath.num) return;//即使是装了剩下的所有程序也无法成为最优
// if (index == n)
// { //已经完成了对n件物品的选择
// if (cur.num > maxPath.num || (cur.num == maxPath.num && maxPath.len < maxPath.len))
// maxPath = cur;
// return;
// }
// DFS(index + 1, cur);//不选择第index件物品
//
// cur.p[cur.num++] = L[index];cur.len += L[index];
// DFS(index + 1, cur);
//
//}
//
//int main()
//{
// while (scanf("%d %d", &n, &len))
// {
//
// for (int i = 0; i < n; i++) scanf("%d", &L[i]);
//
// sort(L, L + n, cmp);
//
// Path p;
// p.len = 0;
// p.num = 0;
// DFS(0, p);
//
// printf("%d %d\n", maxPath.num, maxPath.len);
// for (int i = 0; i < maxPath.num; i++)
// if (i != n - 1) printf("%d ", maxPath.p[i]);
// else printf("%d\n", maxPath.p[i]);
//
// }
//
// return 0;
//}
// //WA解决办法:保存排序索引 //#include <iostream>
//#include <cstring>
//#include <algorithm>
//using namespace std;
//
//const int MAX = 605;
//int n, len, L[MAX],ind[MAX];
//
//struct Path
//{
// int num;
// int len;
// int p[MAX];
// int inx[MAX];
//
//}maxPath;
//
//void BubbleSort(int *p, int length, int * ind_diff)
//{
// for (int m = 0; m < length; m++)
// {
// ind_diff[m] = m;
// }
//
// for (int i = 0; i < length; i++)
// {
// for (int j = 0; j < length - i - 1; j++)
// {
// if (p[j] > p[j + 1])
// {
// int temp = p[j];
// p[j] = p[j + 1];
// p[j + 1] = temp;
//
// int ind_temp = ind_diff[j];
// ind_diff[j] = ind_diff[j + 1];
// ind_diff[j + 1] = ind_temp;
// }
// }
// }
//}
//
////DFS,index为当前处理的物品编号
//void DFS(int index, Path cur)
//{
// if (cur.len > len) return;//长度超了
// if (index == n)
// { //已经完成了对n件物品的选择
// if (cur.num > maxPath.num || (cur.num == maxPath.num && maxPath.len < maxPath.len))
// maxPath = cur;
// return;
// }
// DFS(index + 1, cur);//不选择第index件物品
//
// cur.p[cur.num] = L[index]; cur.len += L[index], cur.inx[cur.num++] = ind[index];
// DFS(index + 1, cur);
//
//}
//
//int cmp(int a, int b)
//{
// return a < b;
//}
//
//int main()
//{
// while (cin>>n>>len)
// {
//
// for (int i = 0; i < n; i++) cin >> L[i];
//
// int *save = new int[MAX];
// memcpy(save, L, sizeof(L));
//
// BubbleSort(L, n, ind);
//
// Path p;
// p.len = 0;
// p.num = 0;
// DFS(0, p);
//
// cout << maxPath.num << " " << maxPath.len << endl;
//
// int *inx = new int[MAX];
// memcpy(inx, maxPath.inx, sizeof(maxPath.inx));
//
// for (int i = 0; i < maxPath.num; i++)
// if (i != maxPath.num - 1) cout << inx[i] << " ";
// else cout << inx[i] << endl;
//
// sort(inx, inx + maxPath.num, cmp);
//
// for (int i = 0; i < maxPath.num; i++)
// if (i != maxPath.num - 1) cout << save[inx[i]] << " ";
// else cout << save[inx[i]] << endl;
//
// }
//
// return 0;
//} //超时解决办法:换用贪心算法
//结果还是超时。。。。。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; const int MAX = ;
int n, len, L[MAX], save[MAX], mnum; struct Path
{
int num;
int len;
int p[MAX]; }maxPath; //DFS,index为当前处理的物品编号
void DFS(int index, Path cur, int remain)
{
if (cur.num == mnum)
{ //已经选择mnum件物品
if (cur.len > maxPath.len && cur.len <= len)
maxPath = cur;
return;
} if (index >= n) return; if (cur.len + remain < maxPath.len) return; //if (cur.len + L[index] > len) return;这不应该加，如果加了大于len长度的不选和选择两种DFS都没有机会了，就丧失了不选之后的DFS遍历，结果就少了。
//至少不应该加在这里 DFS(index + , cur, remain - L[index]);//不选择第index件物品 if (cur.len + L[index] <= len)
{
cur.len += L[index]; cur.p[cur.num++] = L[index];
DFS(index + , cur, remain - L[index]);
}
} int cmp(int a, int b)
{
return a < b;
} //arr,程序长度数组, r,已经使用程序的长度
int find_most(int arr[])
{
sort(arr, arr + n, cmp);
int i = , remain = len;
for (; i < n; i++)
{
remain -= arr[i];
if (remain <= ) return i;
}
return i;
}
void init(Path &a)
{
a.len = ;
a.num = ;
a.p[a.num] = { }; } int main()
{
while (cin >> n >> len)
{
int remain = ;
for (int i = ; i < n; i++)
{
cin >> L[i];
save[i] = L[i];
remain += L[i];
} //find most program number
mnum = find_most(save); Path cur;
init(cur);
init(maxPath); //init && DFS
DFS(, cur, remain); //print ans
cout << mnum << " " << maxPath.len << endl;
for (int i = ; i < maxPath.num; i++)
if (i != maxPath.num - ) cout << maxPath.p[i] << " ";
else cout << maxPath.p[i] << endl; } return ;
}
最新文章
- 使用MyEclipse 9.0 创建 struts2 的HelloWorld 工程
- 有WebService的项目中写applicationContex.xml文件时应注意！！！
- 2016.8.14 HTML5重要标签及其属性学习
- zw版·全程图解Halcon控件安装（delphi2007版）
- 【Leetcode】【Hard】Merge Intervals
- [C] zlstdint（让VC、TC等编译器自动兼容C99的整数类型）V1.0。支持Turbo C++ 3等DOS下的编译器
- MyEclipse中拷贝J2EE项目，发布到tomcat中名字一样的解决办法
- JavaScript函数参数与调用
- java 金额计算，商业计算 double不精确问题 BigDecimal，Double保留两位小数方法
- perl 学习笔记
- Android Material Design 之 Toolbar的使用
- ubuntu 安装LaTex
- 世纪互联、微软Azure与无穷小微积分
- 简单vector达到
- docker - 容器里安装ssh
- Servlet第一篇【介绍Servlet、HTTP协议、WEB目录结构、编写入门Servlet程序、Servlet生命周期】
- ChatGirl 一个基于 TensorFlow Seq2Seq 模型的聊天机器人[中文文档]
- MFC的两个问题
- Android百分比布局支持库（android-percent-support）
- Spring Boot配置文件详解-ConfigurationProperties和Value优缺点-（转）好文