如何设计算法解决长尾词的背包问题？

本文共计1072个文字，预计阅读时间需要5分钟。

《研究僧课程系列文章参考文献》

一个旅行者准备随身携带一个背包，背包容量为n。背包内可以放入多种物品，每种物品的重量和价格分别为wj和vj。问题是如何选择物品放入背包，使得背包内物品的总价值最大，同时不超过背包的容量。

研究生课程系列文章参见索引《在信科的那些课》题目一个旅行者准备随身携带一个背包可以放入背包的物品有n种每种物品的重量和价值分别为wj,vj.如果背

研究生课程系列文章参见索引《在信科的那些课》

题目

一个旅行者准备随身携带一个背包可以放入背包的物品有n种每种物品的重量和价值分别为wj, vj . 如果背包的最大重量限制是b, 怎样选择放入背包的物品以使得背包的价值最大? 目标函数 约束条件

算法设计

设Fk(y) 表示只允许装前k 种物品,背包总重不超过y 时背包的最大价值。Fk(y)有两种情况不装第k件物品或至少装1件第k种物品。 如果不装第k件物品那么只能用前k-1件物品装入背包背包的限制重量仍为y所以最大价值是Fk-1(y) 如果装1件第k件物品那么装入的第k件物品价值为vk重量为wk剩下的物品仍要在前k件里选择因为每件物品可以装多件如果只能装1件就是在前k-1件里选择。于是问题规约为背包限制重量y-wk的情况下前k件物品取得最大价值即Fk(y-wk)vk。