首页 > 其他 > 详细

01背包之为什么逆序

时间:2020-02-25 16:31:41      阅读:52      评论:0      收藏:0      [点我收藏+]

既然来到了这一步,则对01背包有一定的了解了

重要的来了。。。。。。。

 dp[v]=max(dp[v],dp[v-c[i]]+w[i]);    关于这个01背包因为每个物品只有一件所以每个物品最多只能拿一个
所以对于dp[v]是由dp[v-c[i]]得来 反例:如果正序的话则在处理i物品的时候 先是处理dp[v-c[i]]的容量如果这个时候放进去了i物品,在处理dp[v]的时候可能还能放进去i物品就重复了,所以不能逆序

01背包之为什么逆序

原文:https://www.cnblogs.com/chaiyinlei/p/12362158.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!