回溯算法之购物车(0-1 背包问题)
【摘要】 1、问题（参考趣学算法）
央视有一个大型娱乐节目— 购物街,舞台上模拟超市大卖场,有很多货物,每个嘉宾分配一个购物车,可以尽情的装满购物车,购物车装的价值最高者取胜。假设 n 个物品和 1个购物车,每个物品 i 对应价值为 vi,重量 wi,购物车的容量为 W(你也可以将重量设定为体积)。每个物品只有一件,要么装入,要么不装入,不可拆分。如何选取物...
1、问题（参考趣学算法）
央视有一个大型娱乐节目— 购物街,舞台上模拟超市大卖场,有很多货物,每个嘉宾分配一个购物车,可以尽情的装满购物车,购物车装的价值最高者取胜。假设 n 个物品和 1个购物车,每个物品 i 对应价值为 vi,重量 wi,购物车的容量为 W(你也可以将重量设定为体积)。每个物品只有一件,要么装入,要么不装入,不可拆分。如何选取物品装入购物车,使购物车所装入的物品的总价值最大?要求输出最优值(装入的最大价值)和最优解(装入了哪些物品)。
2、分析
从 n 个物品中选择一些物品,相当于从 n 个物品组成的集合 S 中找到一个子集,这个子集内所有物品的总重量不超过购物车容量,并且这些物品的总价值最大。S 的所有的子集都是问题的可能解,这些可能解组成了解空间,我们在解空间中找总重量不超过购物车容量且价值最大的物品集作为最优解
1）、算法设计
(1)定义问题的解空间
购物车问题属于典型的 0-1 背包问题,问题的解是从 n 个物品中选择一些物品使其在不
超过容量的情况下价值最大。每个物品有且只有两种状态,要么装入购物车,要不不装入。那么第 i 个物品装入购物车,能够达到目标要求,还是不装入购物车能够达到目标要求呢?很显然,目前还不确定。因此,可以用变量 xi 表示第 i 种物品是否被装入购物车的行
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/80233874
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）