整数01背包问题

2017年9月7日11:55:36 发表评论 19

小偷有一个容量为W的背包,有n件物品,第i个物品价值vi,且重wi

目标: 找到xi使得对于所有的xi = {0, 1}

sum(wi*xi) <= W, 并且 sum(xi*vi)最大

 

暴力回溯法怎么写?

去冗余?

自底向上(递推)

滚动数组

空间复杂度O(W)

01背包解决的范围,W不大,n很大,必须是整数

 

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: