当前位置：首页 > news >正文

【算法 | 实验8】分配最小页数（数组划分和最大值最小化问题）

news 来源：原创 2024/5/20 0:40:17

文章目录

题目
问题分析与算法设计思路
- 思路1：类似枚举的分治（暴力）
- 思路2：二分法
算法实现（C++）
- 思路1实现
- 思路2实现
bug记录
- 1、子问题对最大值没有实现最小化
- 2、保存的最大值是局部的
运行结果
算法分析

题目

分配最小页数 （学校OJ 357题）
给定n本书的页数，m名学生。这些书按页数的升序排列成一个序列。每个学生都被分
配去读一些序列中连续的书。设分配给第i个学生的书籍的总页数为Pi，1<=i<=m。找出
优化的分配方式，使得最大的Pi最小。用分治法求解。
输入描述
第一行输入t，表示t个测试用例
对于每一个测试用例第一行输入n和m，表示书的数量和学生的数量
第二行按升序输入n个整数，表示书的页数。
输出描述
t行，表示t个测试用例的解
样例输入
2
4 2
12 34 6790
15 7
12 34 67 90 95 103 150 165 170 198 201 235 240 245 251
样例输出
113
436

问题分析与算法设计思路

思路1：类似枚举的分治（暴力）

基本思路：我们这样划分问题，不妨使第一个同学看书 x 页；而剩余的书和同学则构成一个原问题的子问题，使剩余同学中看书最多的同学看了 y 页。那么所有同学中的最大页数 $z = ma x (x, y)$ 。
而对于剩余的书和同学，我们继续划分为一个同学和其它剩余的同学。直到只剩下一个同学时，就不可再分，组合这些子问题的解将得到最初原问题的解。

思路2：二分法

在思路1中，我们以同学为主要对象进行，通过改变给同学分配的书的数量，来搜索解空间。

基本思路：这里对问题引入一种新的描述，以方便理解。我们把每个同学看作一个桶，而每本书看作一个物品，书的页数就是物品的大小。每个桶有一个最大容量，分配书籍就是将物品一个个放入桶中，当一个桶放不下时，就将物品放到下一个桶中。那么问题就变成了，要找一个最小桶容量，而恰好能将所有的物品都放进桶中。

因此，这里问题的主要对象是桶的容量。

算法过程：对桶容量进行二分搜索，找到最小桶容量。

首先确定一个桶容量的大致范围。不妨令第 i 个物品的大小为 $a [i]$ ，所有物品大小和为 sum，则桶容量的初始区间为 $[a [m], s u m]$ （m 为物品数量）。

搜索：
设初始搜索区间为 $[f i rs t, e n d]$

先取中间值 $mi d = (f i rs t + e n d) /2$ ，然后对容量 mid 进行判断
恰好合适，可以放下所有物品，但桶容量再减小 1 就放不下了。
桶小了，放不下所有物品，则搜索区间的右边 $[mi d + 1, e n d]$
桶大了，能放下所有物品，但不是恰好合适，则搜索区间左边 $[f i sr t, mi d - 1]$ 。
递归求解。

判断桶能否放下所有物品：

遍历物品序列，逐个放入桶中。若需要桶的数量大于 m，则桶容量小了。

算法实现（C++）

思路1实现

#include<iostream>
using namespace std;
const int Big = 8848;//用作极大值 
int renshu;//学生人数 

 
int anser(int m,int n,int l,int r,int a[])//表示m堆书，n个学生在分摊之后，返回学生所看书的最大页数 
{
//	cout<<"m="<<m<<" n="<<n<<" l="<<l<<endl;
	int answer = 0;
	if(n == 1)
	{
		int sum = 0;
		for(int i = l; i <= r; i++)
		{
			sum += a[i];
		}
		answer = sum;
		goto label;
	}
	if(m == n)
	{
		answer = a[r];
		goto label;
	}
	if(m < n)
	{
		answer = Big;
		goto label;
	}
	if(m > n)
	{
		int minOfMax = Big;
		int sum = 0;
		for(int i = l; i <= m - n + l; i++)
		{
//			cout<<"-------------------i="<<i<<"  m-n+l= "<<m-n+l<<endl;
			sum += a[i];
			int t = anser(m-i+l-1, n-1, i+1, r, a);
			int maxNum = max(sum, t);//原问题分成两部分，取最大值 
			
			if(maxNum == 13)
			{
				system("pause");
			}
			
			minOfMax = min(minOfMax, maxNum);
		}
		answer = minOfMax;
	}
label:
	return answer;
}

int main()
{
	int t,m,n;
	cin>>t;//t表示测试案例数 
	for(int j=0;j<t;j++)
	{
		cin>>m>>n;//m表示书堆的数目，n表示学生数目 
		renshu=n;
		int *a=new int[m+1];
		for(int i=0;i<m;i++)
			cin>>a[i];	
		int answer = anser(m,n,0,m-1,a);//递归求解 
		cout<<"answer: "<<answer<<endl;
		delete [] a;
	}
	return 0;
} 
/*测试数据
2
4 2
12 34 67 90
15 7
12 34 67 90 95 103 150 165 170 198 201 235 240 245 251
*/

思路2实现

运行

在这里插入图片描述

代码
为了方便展示运行效果，代码中嵌入了一些输出中间变量值的语句。而且在 main 函数中仅安排了一个测试用例的输入。

#include<iostream>
using namespace std;

int TwoPointSearch(int f, int e, int a[], int n, int m);
bool Can(int a[], int n, int x, int m);


int main(){
	int n = 0;//物品数量
	int m = 0;//桶的数量 
	int sum = 0;//物品大小之和 
	cin >> n >> m;
	int *a = new int[n];
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	int answer = TwoPointSearch(a[n-1], sum, a, n, m);
	cout<<"answer:"<<answer<<endl; 
	return 0;
}

int TwoPointSearch(int f, int e, int a[], int n, int m)
{
	//返回：能装下的最小桶容量
	cout << "arange:" << f << " " << e;
	
	int mid = (f + e) / 2;
	bool can = Can(a, n, mid, m);
	
	cout << "  can:" << can;
	cout << "  mid:" << mid << endl;
	
	if(can)
	{
		int can_smaller = Can(a, n, mid-1, m);
		if(! can_smaller)
		{
			return mid;
		}
		else
		{
			return TwoPointSearch(f, mid-1, a, n, m);
		}
	}
	else
	{
		return TwoPointSearch(mid+1, e, a, n, m);
	}
}

bool Can(int a[], int n, int x, int m)
{
	//放得下吗？
	//n:物品数，m:桶数 
	int flag = false; //to test 
	
	if(x < a[0])
	{
		return false;
	}
	
	int need = 0;//需要桶的数量
	int sum = 0;//一个桶已经装了多少 
	
	for(int i = 0; i < n; i++)
	{
		if(sum + a[i] <= x)
		{
			sum += a[i];
		}
		else
		{
			sum = a[i];
			need++;
		}
		if(need + 1 > m)
		{
			return false;
		}
	} 
	
	return true;
}

bug记录

1、子问题对最大值没有实现最小化

问题分析
answer这个全局变量很不好，破坏了递归的逻辑。

本来要分治，前面一部分就是k，然后后面是剩余部分的最小化最大值。

代码里是用什么实现最大值的最小化的？就是answer，但answer之会在递归的第一层更新。

也就是说，对分治后的后面一段子数组，并没有实现最大值的最小化。

解决方案（见思路1实现）
改用将 answer 作为函数内的局部变量的写法。

问题代码版本

#include<iostream>
using namespace std;
int answer=100000;
int maxsize=1;
int renshu;
int anser(int m,int n,int l,int r,int a[])//表示m堆书，n个学生在分摊之后，返回学生所看书的最大页数 
{
//	cout<<"m="<<m<<" n="<<n<<" l="<<l<<endl;
	if(n==1)//如果只有一个学生，就直接返回a数组中的值之和 
	{
		int sum=0;
		for(int i=l;i<=r;i++)
		{
			sum+=a[i];
		}
		return sum;
	}
	else if(m==n)//若书堆数和学生数相同，因为要保证每个学生都有书看，而且数组a已经排好序了，所以直接返回最后一个数即可 
	{
		return a[r];
	}
	else if(m<n)//此种情况会导致有学生没有书看，所以返回零（这个不大确定，我是乱写的） 
	return 0;
	else if(m>n)//当书堆数大于学生人数时 
	{
		int k=0;
		for(int i=l;i<=m-n+l;i++)//表示列举可能的组合 ...这里不知道咋解释 
		{
			k+=a[i];
			maxsize=max(k,anser(m-i+l-1,n-1,i+1,r,a));
			if(n==renshu)
			{
				answer=min(answer,maxsize);
			}
		}
	}
}

int main()
{
	int t,m,n;
	cin>>t;//t表示测试案例数 
	for(int j=0;j<t;j++)
	{
		cin>>m>>n;//m表示书堆的数目，n表示学生数目 
		renshu=n;
		int *a=new int[m+1];
		for(int i=0;i<m;i++)
		cin>>a[i];	
		anser(m,n,0,m-1,a);//递归求解 
		cout<<answer;
		delete [] a;
		answer=100000;
	}
	return 0;
 }

2、保存的最大值是局部的

问题分析
可以对比思路1实现。原来b也通过answer返回了，到上一层求b又有一次max的筛选，得到的才是最大值。
直接将b保存下来，只经过了与本层k的比较，就相当只比较了两个人的看书量，不是该分配情况下所有人看书最多的那一个。

b数组应该存的是若干个最大值，然后通过排序最小化最大值。现在你代码并没有保证存的b是个“最大值”

问题代码版本

#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
int renshu,book;
vector<int>v;
vector<int>::iterator it;
int maxsize=100000;
void anser(int m,int n,int l,int r,int a[],int &b)//表示m堆书，n个学生在分摊之后，返回学生所看书的最大页数 
{
	if(n==1)
	{
		int sum=0;
		for(int i=l;i<=r;i++)
		{
			sum+=a[i];
		}
		b=sum;
		return ;
	}
	else if(m==n)
	{
		b=a[r];
		return ;
	}
	else if(m<n)
	{
		b = 8848;
		return;
	}
	else if(m>n)
	{
		int k=0;
		for(int i=l;i<=m-n+l;i++)
		{
			if(n==1)
			break; 
			else if(m==n)
			break;
			k+=a[i];
			int temp;
			anser(m-i+l-1,n-1,i+1,r,a,temp);
			b=max(k,temp);
			
			v.push_back(b);
		}
		return;
	}
}

int main()
{
	int t,m,n,b=0,sum=0;
	cin>>t;//t表示测试案例数 
	for(int j=0;j<t;j++)
	{
		sum=0;
		cin>>m>>n;//m表示书堆的数目，n表示学生数目 
		book=m;
		renshu=n;
		int *a=new int[m+1];
		for(int i=0;i<m;i++)
		{
			cin>>a[i];
			sum+=a[i];
		}
		if(n==1)
		cout<<sum<<endl;
		else if(m==n)
		cout<<a[m-1]<<endl;
		else
		{
			anser(m,n,0,m-1,a,b);//递归求解 
			sort(v.begin(),v.end());
			cout<<*v.begin()<<endl;
		}	
		delete [] a;
	}
	return 0;
 }