关于背包问题,其实可以分为两种类型:0-1背包问题 和 部分背包问题。 1、先通过一个例子来说明一下二者的区别吧! 有一个窃贼在偷窃一家商店时发现有n件物品,第i件物品价值为vi元,重量为wi,假设vi和wi都为整数。他希望带走的东西越值钱越好,但他的背包中之多只能装下W磅的东西,W为一整数。他应该带走哪几样东西? 0-1背包问题:每件物品或被带走,或被留下,(需要做出0-1选择)。小偷不能只带走某个物品的一部分或带走两次以上同一个物品。 部分背包问题:小偷可以只带走某个物品的一部分,不必做出0-1选择。…

2013年11月13日 0条评论 5点热度 阅读全文