algorithm - 以最大利润做某事的动态算法

Question

问题是:想象一个学生有 n 个项目和 m 时间来完成这些项目。他必须管理自己的时间以获得他能获得的最高分。

通过在每个项目上工作 1 小时，他可以获得不同的分数。
例如，在项目 1 上工作一小时，他可以获得 2 分，如果他在项目 1 上工作两个小时，他可以获得 2.25 分。
项目 2 不同 - 在项目 2 上工作 1 小时，他可以获得 1 分，但在项目 2 上工作两个小时，他可以获得 2.5 分。

另一个例子:

m = 5 和 n = 10。表示有 5 个项目和 10 小时的时间来完成这些项目。

projectnumber  hours to complete   1 hour work  2h work  3h work  4h work    
     1                3                1.5        2        2.25     _
     2                4                0.5        1.75     2        2.25
     3                3                2          2.25     2.5      _
     4                2                1          2        _        _
     5                5                1          2        2.5      3

我能理解的:

经过思考，我明白这就像作业调度，也许解决这个问题的最佳算法是动态规划算法。

首先，您应该考虑项目的第一个小时。并按利润降序排序。

2  1.5  1   1   0.5

完成项目 3 的第一个小时后，您应该将项目 3 的第二个小时添加到列表中(剩余 9 个小时)。

1.5  1   1   0.5  0.25 (0.25 is for second hour of project 3)

它应该持续到您必须完成项目的 10 个小时结束。

但我确信这个算法有一些问题。其中之一是，也许项目的第二个小时会让你捕获一个好点。所以你不能只考虑项目的第一个小时。

有什么建议吗？

Answer 1

您的问题似乎类似于 0-1 背包问题:-

1. Total hours m is that knapsack capacity
2. consider each number of hours and corresponding points as an item weight and value
3. Maximize the points.

0-1 背包问题在伪多项式时间内的 DP 解。

第 N 个项目的问题公式:-

Knapsack(N,M) = max(Knapsack(N-1,M),Knapsack(N-1,M-1)+Points[N][1]+Knapsack(N-1,M-2)+Points[N][2]......)

注意:-点数[N][k] = 在项目 N 上工作 k 小时获得的点数

Knapsack Problem