algorithm – 0-1背包带分区约束

栏目: 编程工具 · 发布时间: 5年前

内容简介:我有一个问题,表面看起来像0-1背包.我有一组可以选择(或不选择)的可能“候选人”,每个候选人都有“权重”(成本)和潜在的“价值”.如果这是整个问题,我会使用DP方法并完成它.但是这里是曲线球:对最终解决方案中可能存在的候选者存在“分区约束”.我的意思是候选空间被分成不连续的等价类.对于我的特殊问题,大约有300个候选人和12个可能的等同类.有“商业规则”说我只能说C1级的3名候选人和C2级的6名候选人等.这个约束建议使用分支定界技术或其他形式的修剪的图搜索类型方法,但是我有点难以理解如何开始,因为我只熟悉

我有一个问题,表面看起来像0-1背包.我有一组可以选择(或不选择)的可能“候选人”,每个候选人都有“权重”(成本)和潜在的“价值”.如果这是整个问题,我会使用DP方法并完成它.但是这里是曲线球:对最终解决方案中可能存在的候选者存在“分区约束”.

我的意思是候选空间被分成不连续的等价类.对于我的特殊问题,大约有300个候选人和12个可能的等同类.有“商业规则”说我只能说C1级的3名候选人和C2级的6名候选人等.

这个约束建议使用分支定界技术或其他形式的修剪的图搜索类型方法,但是我有点难以理解如何开始,因为我只熟悉0-1背包的DP解决方案.哪些技术/方法可能适合这个问题?我还想过可能使用约束编程库但不确定它是否能够找到解决方案?

您可以尝试使用整数线性规划求解器,其中有一个二元变量用于选择每个候选.约束很容易表示为线性不等式.有300个变量,求解器解决它时不会有太多麻烦.

最简单的方法可能是以文本格式(如 CPLEX LP format )编写问题,然后使用Coin CBC或GLPK等求解器.

翻译自:https://stackoverflow.com/questions/9143885/0-1-knapsack-w-partitioning-constraints


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

简约至上

简约至上

[英] Giles Colborne / 李松峰、秦绪文 / 人民邮电出版社 / 2011-1-1 / 35.00

追求简单易用是人类的本性,无论是互联网产品。还是移动应用。亦或其他交互式设计,简单易用始终都是赢得用户的关键。同时,简单易用的程度也与产品寿命的长短密切相关。在《简约至上:交互式设计四策略》中,作者Giles托20多年交互式设计的探索与实践。提出了合理删除、分层组织、适时隐藏和巧妙转移这四个达成简约至上的终极策略,讲述了为什么应该站在主流用户一边,以及如何从他们的真实需求和期望出发,简化设计,提升......一起来看看 《简约至上》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具