动态规划练习算法
dynamic programming practice algorithm
我试图找到以下问题的递归关系和算法，但已经卡了几天：
总共有 H > n 小时的工作时间 n 学校项目（所有这些都在同一时间到期），你想现在决定分配这次时间。为简单起见，假设 H 是一个正整数，并且您将在每个项目上花费整数小时。你想出了一组函数 f1, ..., fn（当然是粗略估计）如果在项目上工作 x 小时，我会给你 f[=46= 的分数]i(x) 在那个项目上。
可以假定 fi(x) 如果 x 增加，每个项目将按 1 到 100 的等级评分。
所以，给定 H 和 f1, ..., fn，你需要确定你将在每个项目上花费多少（整数）小时，以便你的平均成绩尽可能大（最大成绩）。
- 寻找 G[H, j] 的递归关系，其中 G[H,j]是花费H[=获得的等级总和55=] 课程 1、2、... 项目的总时数 j
- 寻找计算 G[H, n][= 的动态规划算法84=]
有人有想法吗？
我认为这可行：
G[H<0, j] = -Infinity
G[H, 0] = 0
G[H, j] = max(G[H-i, j-1]+f_j(i)) for 0<=i<=H
在重复中，我试图找到在项目 j 上工作的最佳小时数。这个解是 O(H^2*n).
我试图找到以下问题的递归关系和算法，但已经卡了几天：
总共有 H > n 小时的工作时间 n 学校项目（所有这些都在同一时间到期），你想现在决定分配这次时间。为简单起见，假设 H 是一个正整数，并且您将在每个项目上花费整数小时。你想出了一组函数 f1, ..., fn（当然是粗略估计）如果在项目上工作 x 小时，我会给你 f[=46= 的分数]i(x) 在那个项目上。
可以假定 fi(x) 如果 x 增加，每个项目将按 1 到 100 的等级评分。
所以，给定 H 和 f1, ..., fn，你需要确定你将在每个项目上花费多少（整数）小时，以便你的平均成绩尽可能大（最大成绩）。
- 寻找 G[H, j] 的递归关系，其中 G[H,j]是花费H[=获得的等级总和55=] 课程 1、2、... 项目的总时数 j
- 寻找计算 G[H, n][= 的动态规划算法84=]
有人有想法吗？
我认为这可行：
G[H<0, j] = -Infinity
G[H, 0] = 0
G[H, j] = max(G[H-i, j-1]+f_j(i)) for 0<=i<=H
在重复中，我试图找到在项目 j 上工作的最佳小时数。这个解是 O(H^2*n).