首页 > 代码库 > 六月二十日 上午（深搜）
六月二十日 上午（深搜）
1最佳调度问题
题目描述
假设有n个任务由k个可并行工作的机器来完成。完成任务i需要的 时间为ti。试设计一个算法找到出完成这个n个任务的最佳调度，使得完成全部任务的时间最早。
对任意给定的整数n和k，以及完成任务i需要的时间为ti，1<=i<=n。编程计算完成这n个任务的最佳调度。
n<=20,k<=8
输入
第1 行有2个正整数n 和k。第2行的n个正整数是完成n 根任务需要的时间。
输出
计算出的完成全部任务的最早时间
样例输入
7 3 2 14 4 16 6 5 3
样例输出
17
这道题读完有点蒙，一开始想的是深搜每一个点，然后发现怎么调都不对
再仔细一想，把每个机器当做容器，不停地把每个任务，放在每个容器里，
排列组合一下，再用两个剪枝。
这里有一个技巧，就是可以先贪心算出一个比较好的解，然后用这个解去
减掉深搜时候的大多数枝干，可以提高速度
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n,k,ans,a[1001],s[1001]; bool cmp(int a,int b) { return a>b; } int readin() { int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘;ch=getchar(); } return x; } void dfs(int x,int y) { int i,j; if(y>=ans) return; if(x>n) { ans=y; return; } for(i=1;i<=k;i++) { s[i]+=a[x]; if(s[i]<ans) dfs(x+1,max(y,s[i])); s[i]-=a[x]; } } int main() { int i; n=readin(); k=readin(); for(i=1;i<=n;i++) a[i]=readin(); sort(a+1,a+n+1,cmp); ans=50000000; s[1]=a[1]; dfs(2,a[1]); printf("%d",ans); return 0; }
六月二十日 上午（深搜）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。