c语言的动态规划算法的这道题怎么做啊,求大神!!!
发布网友
发布时间：2023-07-10 08:33
共1个回答
热心网友
时间：2024-09-29 13:23
申请二维数组 dp[N+1][M+1]。
1. dp[0][j]，0<=j<=m，表示一种题型都不选择并且竞赛总时间为 j 时最多得分，显然等于 0。
2. dp[i][0]，1<=i<=n，表示只选择竞赛题型 0..i-1 并且竞赛总时间为 0 时最多得分，显然等于0。
3. dp[i][j]，1<=i<=n，1<=j<=m，表示最多只选择竞赛题型 0..i-1 并且竞赛总时间为 j 时最多得分。
3.1 如果不选择第 i-1 种题型，则最多得分 dp[i][j] = dp[i-1][j]。
3.2 如果只选择 1 道第 i-1 种题型，则最多得分 dp[i][j] = 1*point[i-1] + dp[i-1][j-time[i-1]]。
3.3 如果只选择 2 道第 i-1 种题型，则最多得分 dp[i][j] = 2*point[i-1] + dp[i-1][j-2*time[i-1]]。
...
3.k+1 最多可以选择 k=j/time[i-1] 道第 i-1 种题型，则最多得分 dp[i][j] = k*point[i-1] + dp[i-1][j-k*time[i-1]]。
以上 k+1 种情况中的最大值即为 dp[i][j] 的最多得分，即 dp[i][j] = max(dp[i-1][j], 1*point[i-1] + dp[i-1][j-time[i-1]], 2*point[i-1] + dp[i-1][j-2*time[i-1]], ..., dp[i][j] = k*point[i-1] + dp[i-1][j-k*time[i-1]])， 即 dp[i][j] = max(k*point[i-1] + dp[i-1][j-k*time[i-1]]|0<=k<=j/time[i-1])。
最终 dp[N][M] 即为最多分数。
从 dp 最后一行依次往第一行即从最后一种题型开始往第0种题型求每种题型选择的题目数。
设当前行为 i，列为 j，最多分数为 p，则求出 k（0<=k<=j/time[i-1]），使得 p == k*point[i-1] + dp[i-1][j-k*time[i-1]]，则 k 为第 i-1 种题型选择的题目数。令 j -= k*time[i-1]，p -= k*point[i-1]，后求 dp[i-1] 行即第 i-2 种题型选择的题目数。
具体代码见附件。
