sho*_*ole 8 algorithm dynamic-programming
虽然标准的背包问题可以通过动态编程来解决,但我试图稍微扭转问题以清除我的概念,但是我发现它可能比我想象的更难.
原始的背包问题是,给定一个带有尺寸的背包W,以及一个重量w[i]和有一个值的物品清单v[i],找到能够适合具有最高总价值的背包的物品子集.
据我所知,这可以通过O(Wn)动态编程来完成,其中n是项目数.
现在,如果我尝试添加m约束,它们中的每一个都是一对只能相互挑选的项目(即如果存在项目A和项目B的约束,那么我只能选择其中一个而不是两个)
在这样的约束下,这个问题仍然可以通过动态编程解决O(Wn)吗？
假设:每个元素都包含在最多一个约束中.
对于通常的背包问题,问题表现出的最佳子结构如下:
对于每个项目,可能有两种情况:
1.该项目包含在解决方案中
2.该项目未包含在解决方案中.
因此,n项目的最佳解决方案由以下两个值的最大值给出.
1. n-1物品和W重量获得的最大值.
2. v_n+ n-1项目和W-w_n重量获得的最大值.
现在,如果我们添加第一项n或(n-1)第二项中的任何一项可以存在于解决方案中的约束,那么项的最优解n是由以下三个值的最大值给出的.
1. n-2物品和W重量获得的最大值.
2. v_n+ n-2项目和W-w_n重量获得的最大值.
3. v_(n-1)+ n-2项目和W-w_(n-1)重量获得的最大值.
因此,我们将约束中的每对元素视为单个元素,并O(Wn)及时执行动态编程算法.