网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)
Xidian Online Judge WebBoard
[ New Thread ]
Problem 1146 >> 题解疑问
13030410035 @ 2016-04-24 12:38:25
[ Quote ] [ Edit ] [ Delete ] 1#
题解的思想不就是01背包问题吗,时间复杂度如何优化到O(∑vi)的啊?另外能不能给个详细题解啊
Furude_Rika @ 2016-04-25 07:53:35
[ Quote ] [ Edit ] [ Delete ] 2#
其实这题是个完全背包 求得不是在一定重量下的最大价值 而是求价值一定的时候重量的最小值
dp[0]=0;
for(i=1;i<=m;i++){
for(j=maxn;j>=v[i];j--){
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
这么弄就可以了 然后再看看有哪些dp[j]<W 取个最大的j就可以了
forlfs @ 2016-04-25 09:06:38
[ Quote ] [ Edit ] [ Delete ] 3#
这样写的时间复杂度不是O(n*∑vi)吗?
xry111 @ 2016-04-25 10:20:11
[ Quote ] [ Edit ] [ Delete ] 4#
妈的智障,写题解的时候脑残了
xry111 @ 2016-04-25 10:21:01
[ Quote ] [ Edit ] [ Delete ] 5#
确实是n乘上那个
[Top] [Previous Page] [Next Page]
Anything about the Problems, Please Contact Admin:admin
All Copyright Reserved 2010-2014 Xidian ACM Online Judge TEAM
GPL2.0 2003-2014 HUSTOJ Project TEAM