这题今日头条的算法题（任务执行策略）如何解？

任务执行策略

【题目描述】我们有一批任务在 mesos 当中。这批任务要么不依赖其它任务，要么一定恰好依赖于两个任务，并且整个依赖关系会构成一个三角模型：

Job(1, 1)

Job(2, 1) Job(2, 2)

Job(3, 1) Job(3, 2) Job(3, 3)

……

Job(n, 1) Job(n, 2) …… Job(n, n)

如上图，Job(1, 1) 依赖于 Job(2, 1) 和 Job(2, 2)；Job(2, 2) 依赖于 Job(3, 2) 和 Job(3, 3)；对于任意 1 <= i < n, 1 <= j <= n，Job(i, j) 依赖于Job(i + 1, j) 和 Job(i + 1, j + 1)。最后一行的任务没有任务依赖。

这批任务有一个特点，每个任务都需要配合它所依赖的任务来执行。也就是说，一个任务某次运行是有效的，当且仅当至少满足下列一个条件：

1. 该任务不依赖其它任务；

2. 该任务依赖的两个任务都是有效的。

每个任务都预先设定了一个权重 weight(i, j)。现在由于资源上的限制，我们只能挑选其中的 k 个任务来运行。我们希望所有被运行的任务都是有效的，并使得所有运行过的任务的权重之和最大。

输入格式

第一行是两个整数 n 和 k。

接下来 n 行，其中第 i 行 (1 <= i <= n) 包含 i 个整数，给出各个任务的权重。这个三角形也同时描述了任务的依赖关系。

输出格式

输出仅包含一个整数，即所求的最大权重和。

输入样例

3 4

2 3

1 1 1

输出样例

数据规模

对于 30% 的数据，1 <= n, k <= 50；

对于 100% 的数据，1 <= n <= 100，1 <= m <= C(n + 1, 2)，1 <= weight(i, j) <= 1000。

参考答案如下，但是我看不太懂，谁能分析一下最优子结构如何构造，以及sum[][]数组是什么意思、。

   #include <bits/stdc++.h>  
   constintN = 60;  
   constintM = 500 + 10;//动态规划。把三角形翻转一下, 从底部到顶考虑每个元素。  
   //dp[i][j][k]表示考虑到第(i, j)个, 当前选取了k个元素的最大值。  
   //用前缀和维护一下最大值。  
   intdp[N][N][M], sum[N][N], a[N][N], n, m;  
   intmain() {  
       scanf("%d%d", &n, &m);  
       for(inti = 1; i <= n; ++ i) {  
           for(intj = 1; j <= i; ++ j) {  
               scanf("%d", &a[i][j]);  
           }  
       }  
       for(inti = 1; i <= n; ++ i) {  
           for(intj = 1; j <= i; ++ j) {  
               sum[i][j] = sum[i][j - 1] + a[n - j + 1][i - j + 1];  
           }  
       }  
       memset(dp, 200, sizeof(dp));  
       for(inti = 0; i <= n; ++ i) {  
           dp[i][0][0] = 0;  
       }  
       for(inti = 1; i <= n; ++ i) {  
           for(intj = i; j >= 0; -- j) {  
               for(intk = j; k <= m; ++ k) {  
                   dp[i][j][k] = std::max(dp[i][j + 1][k],  
                                          dp[i - 1][std::max(0, j - 1)][k - j] + sum[i][j]);  
               }  
           }  
       }  
       printf("%d\n", dp[n][0][m]);  
       return0;  
   }  

全部评论

推荐最新楼层

波利要吃饼干

北京邮电大学 C++

感觉好难，看了很久，说一下自己的理解。首先，先不考录答案中的翻转，还是想是一个直角在左下角的三角形。要明白如果某一个任务要执行，那么就意味着以这个任务为左上角的直角三角形中的任务必须都执行，这样才能满足依赖。然后，解法中的dp[i][j][k]表示的是考虑到a[n-j+1][i]时且选择他执行的情况下，使得执行任务的个数恰好为k时的最优解。有些绕口..... 重点是这个选择的顺序，根据依赖的特性，如果执行了某个任务，就相当与执行了一个三角形，然后在已经执行的任务所形成的直角三角形斜边上，在从最底层向上像铺台阶一样铺一层，就能满足这一层上的所有依赖！！！所以，这个sum[i][j]其实是从直角三角形的底边，按照从左向右的顺序选择斜边的起点，然后一层一层的判断的。这样就能保证满足依赖了，同时k用来满足个数的限制。画画图就好理解了。所谓的+sum[i][j]就是在第i个斜边上从底向上铺j个任务，dp[i - 1][std::max(0, j - 1)][k - j]则用来满足依赖。

点赞回复分享

发布于 2017-08-21 11:23

肉丝丝

广州大学

看不懂a[n - j + 1][i - j + 1] 是什么

点赞回复分享

发布于 2017-10-17 10:54