• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational mathematics and mathematical physics >On Combinatorial Properties of the Knapsack Problem
【24h】

On Combinatorial Properties of the Knapsack Problem

机译：关于背包问题的组合性质

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The knapsack problem with Boolean variables and a single constraint is studied. In the general case, this problem is NP-hard; for this reason, its exact solution requires the use of various search algorithms with the decomposition of the set of feasible solutions and computation of estimates of the objective function. Combinatorial formulas for computing and estimating the value of the objective function in various cases depending on the set of given parameters of the problem are derived. The case when the coefficients of the constraint vector coincide with the coefficients of the objective function is considered. The relationship between the set of solutions of the problem and threshold functions of a certain type is revealed. The coefficients of the objective function, the coefficients of the constraint vector, and the knapsack size are used as parameters. The classical method of generating functions is used as the basic technique. The results obtained in this paper can be used, in particular, for estimating the complexity of search and decomposition methods of solving the problem and for developing such methods as auxiliary procedures.
机译：研究了布尔变量的背包问题和单个约束。在一般情况下，这个问题是np-hard;因此，其确切的解决方案需要利用各种搜索算法与可行性解决方案集的分解和目标函数的估计的计算。派生了组合公式，用于计算和估计各种情况下的目标函数的值，这取决于问题的给定参数集。考虑约束载体的系数与目标函数的系数重合的情况。揭示了某种问题的解决方案组的关系和某种类型的阈值函数之间的关系。目标函数的系数，约束矢量的系数，以及背裂尺寸用作参数。生成功能的经典方法用作基本技术。特别地，可以使用本文获得的结果，以估计解决问题的搜索和分解方法的复杂性，以及用于开发辅助程序的方法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号