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

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

内容简介：我有一个问题,表面看起来像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

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

查看所有标签

猜你喜欢:

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

码农书籍

How to Solve It

Zbigniew Michalewicz、David B. Fogel / Springer / 2004-03-01 / USD 59.95

This book is the only source that provides comprehensive, current, and detailed information on problem solving using modern heuristics. It covers classic methods of optimization, including dynamic pro......一起来看看《How to Solve It》这本书的介绍吧!

码农工具

RGB转16进制工具

RGB HEX 互转工具

HEX CMYK 转换工具

HEX CMYK 互转工具