问题标题: 酷町堂：1053 最佳调度问题

题目描述 Description
假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。
对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1~n。编程计算完成这n个任务的最佳调度。

输入描述 Input Description
第一行有2 个正整数n和k。第2 行的n个正整数是完成n个任务需要的时间。

输出描述 Output Description
计算出的完成全部任务的最早时间

样例输入 Sample Input
7  3
2  14  4  16  6  5  3
样例输出 Sample Output
17
数据范围及提示 Data Size & Hint
n<=20, k<=6

求思路

刘乐宸在2021-08-14 13:55:52追加了内容

#include <iostream>
using namespace std;
int n, k;
int v[25],w[25], sum, dp[2000][2000];
int main()
{
    cin >> n >> k;
    int zon=0;
    for(int i=1; i<=n; i++)
    {
        cin >> v[i];
        w[i]=v[i];
        zon+=v[i];
    }
    if(k==1)
    {
        cout<<zon;
    }else if(k==2)
    {
        sum=zon/2;
		int n1=n/2;
		for(int i=1; i<=n; i++)
		{
			for(int j=1; j<=sum; j++)
			{
				if(j>=v[i])
				{
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
				}
				else 
				{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		int l, r;
		l=dp[n][sum];
		r=zon-l;
		cout<<max(l,r)<<endl;
    }
    else {
        cout << zon/n;
    }
    return 0;
}

20分打表代码

刘乐宸在2021-08-14 13:55:58追加了内容

#include <iostream>
using namespace std;
int n, k;
int v[25],w[25], sum, dp[2000][2000];
int main()
{
    cin >> n >> k;
    int zon=0;
    for(int i=1; i<=n; i++)
    {
        cin >> v[i];
        w[i]=v[i];
        zon+=v[i];
    }
    if(k==1)
    {
        cout<<zon;
    }else if(k==2)
    {
        sum=zon/2;
		int n1=n/2;
		for(int i=1; i<=n; i++)
		{
			for(int j=1; j<=sum; j++)
			{
				if(j>=v[i])
				{
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
				}
				else 
				{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		int l, r;
		l=dp[n][sum];
		r=zon-l;
		cout<<max(l,r)<<endl;
    }
    else {
        cout << zon/n;
    }
    return 0;
}

20分打表代码