有依赖的背包问题
发布时间:2020-12-13 22:36:03 所属栏目:百科 来源:网络整理
导读:地址:http://blog.csdn.net/mishifangxiangdefeng/article/details/8763361 简化的问题 这种背包问题的物品间存在某种 “ 依赖 ” 的关系。也就是说, i 依赖于 j ,表示若选物品 i ,则必须选物品 j 。为了简化起见,我们先设没有某个物品既依赖于别的物品
地址:http://blog.csdn.net/mishifangxiangdefeng/article/details/8763361 简化的问题
这种背包问题的物品间存在某种“依赖”的关系。也就是说,i依赖于j,表示若选物品i,则必须选物品j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品。 算法这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。
NOIP2006的那道背包问题我做得很失败,写了上百行的代码,却一分未得。后来我通过思考发现通过引入“物品组”和”的概念可以加深对这题的理解,还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系:物品不能既作主件又作附件,每个主件最多有两个附件,可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组,这便揭示了问题的某种本质。 |