0-1背包问题绕开动态规划，分支定界等优化方法

verylazybird · 发表于 2009-12-21 19:20:54

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

基础模型：考虑一个0-1背包问题目的：把该问题复杂化，使传统的动态规划算法，分支定界算法失效，使其只能通过枚举每个方案才能求解。传统的0-1背包问题中，物品的重量和价值都是常量。我打算将其变为物品的价值随着方案不同而变化，物品的重量随着价值的不同而变化，即在模型方程中增加两个价值和重量的n*n的系数矩阵（n为物品总数，矩阵中的每个元素物品和相应项目之间的关系系数）。【注：不考虑模型的物理意义】这样考虑后能够使动态规划算法或其他的优化算法失效吗？或大家有什么其他好的办法吗？不知道有没有描述清楚问题，先谢谢大家！

verylazybird · 发表于 2009-12-23 08:38:26

我的描述可能不是很清楚，附上含具体模型的文档，请大家帮忙看看！多谢！

verylazybird · 发表于 2009-12-23 08:44:20

不好意思，上个帖子没找到在哪儿加附件！再发一遍！

kon3155 · 发表于 2009-12-24 09:55:19

我觉得不考虑模型的物理意义，即使得出结论，也未必在实际问题中用的上物品的价值随着方案不同而变化是可能的，但是物品的重量随着价值的不同而变化就有点想不通了。所以最好有实际问题为背景，才有研究下去的必要性和动力

账号		自动登录	找回密码
密码			欢迎注册

[原创] 0-1背包问题 绕开动态规划，分支定界等优化方法

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

[原创] 0-1背包问题绕开动态规划，分支定界等优化方法