CSU 1945: 最简单的题目
【摘要】
题目：
Description
小明有一台笔记本电脑，一台台式机电脑，两台电脑的性能相同，现在小明手里有N个等待运行的程序，每个程序运行所需的时间分别为n1,n2,n3,n4……，一台电脑同一时刻只能运行一个程序，一个程序只需要运行一次。两台电脑同时开始运行，请问小明该如何分配程序在这两台电脑上运行，使得最后结束运行的电脑的运行...
题目：
Description
小明有一台笔记本电脑，一台台式机电脑，两台电脑的性能相同，现在小明手里有N个等待运行的程序，每个程序运行所需的时间分别为n1,n2,n3,n4……，一台电脑同一时刻只能运行一个程序，一个程序只需要运行一次。两台电脑同时开始运行，请问小明该如何分配程序在这两台电脑上运行，使得最后结束运行的电脑的运行时间最短。
Input
输入不超过30组数据，每组数据第一行为N，代表有N个等待运行的程序，第二行为N个数字，代表每个程序的运行时间，1 <= N <= 1000 ，每个程序的运行时间均为正整数， 所有程序的运行时间之和不超过5000。
思路：
首先是贪心，选出一些数，使得选出的数的总数最接近所有数的总数的一半即可。
其次是动态规划，其实就是0-1背包
代码：
-
#include<iostream>
-
#include<string.h>
-
#include<algorithm>
-
using namespace std;
-
-
int value[1001], ans[5001];
-
-
int main()
-
{
-
int N, V;
-
while (cin >> N)
-
{
-
V = 0;
-
memset(ans, 0, sizeof(ans));
-
for (int i = 1; i <= N; i++)
-
{
-
cin >> value[i];
-
V+= value[i];
-
}
-
for (int i = 1; i <= N; i++)for (int j = V/2; j >= value[i]; j--)
-
ans[j] = max(ans[j], ans[j - value[i]] + value[i]);
-
cout << V - ans[V / 2] << endl;
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/79894585
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）