Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

多重背包时间复杂度问题 #2710

Closed
kjgfcdb opened this issue Oct 7, 2020 · 2 comments
Closed

多重背包时间复杂度问题 #2710

kjgfcdb opened this issue Oct 7, 2020 · 2 comments
Labels
Content Bug / 页面内容有误 Something isn't working help wanted / 需要帮助 Extra attention is needed

Comments

@kjgfcdb
Copy link

kjgfcdb commented Oct 7, 2020 •
edited

我正在访问这个页面（最好带链接）

背包DP

我发现页面有这样的问题

在这一页上，多重背包的朴素算法时间复杂度为O(nW\sum k_i)。请问这里是不是应该去掉sum，使用max比较正确？
@kjgfcdb kjgfcdb added Content Bug / 页面内容有误 Something isn't working help wanted / 需要帮助 Extra attention is needed labels Oct 7, 2020
@welcome
Copy link

welcome bot commented Oct 7, 2020

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～

sbofgayschool added a commit to sbofgayschool/OI-wiki that referenced this issue Oct 7, 2020
@sbofgayschool
Fixed issue OI-wiki#2710.
93d43ee
@sbofgayschool sbofgayschool mentioned this issue Oct 7, 2020
Merged
@sbofgayschool
Copy link
Contributor

sbofgayschool commented Oct 7, 2020 •
edited

感觉应该是 O(W\sum_{i=1}^nk_i) ，已commit到一个pr中

@kjgfcdb kjgfcdb closed this as completed Oct 8, 2020
Enter-tainer added a commit that referenced this issue Oct 9, 2020
@Enter-tainer
Merge pull request #2709 from sbofgayschool/master
dc529c4 
Fixed issue #2710. Rearranged quick sort section and added more stuff.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Content Bug / 页面内容有误 Something isn't working help wanted / 需要帮助 Extra attention is needed
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@kjgfcdb @sbofgayschool