未知题型

分析程序的上界O和下界W。 for w = 0 to W do M[0, w] = 0 for i = 1 to n do for w = 0 to W do if (wi > w) M[i, w] = M[i-1, w] else M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]} return M[n, W] 该程序时间复杂度的上界是O（）、下界是W（_）。

【参考答案】

程序描述了一个典型的动态规划问题，其中涉及到两个嵌套循环：外层循环变量`i`从1到`n`，内层循环变量`w`从0到`W`......

(↓↓↓ 点击下方‘点击查看答案’看完整答案、解析 ↓↓↓)

点击查看答案&解析

单项选择题

单项选择题

未知题型

分析程序的上界O和下界W。 for w = 0 to W do M[0, w] = 0 for i = 1 to n do for w = 0 to W do if (wi > w) M[i, w] = M[i-1, w] else M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]} return M[n, W] 该程序时间复杂度的上界是O（____）、下界是W（_____）。