Question

c语言的动态规划算法的这道题怎么做啊，求大神！！！

题目要求：如何获得最多的分数 输入条件：竞赛所需总时间M，竞赛题型总数N，各种题型的得分和耗时； 输出：获得分数最多的选择题型方法及获得总分。按照这个样例怎么写代码啊？？？

Answer 1

申请二维数组 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 种题型选择的题目数。

具体代码见附件。