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背包问题绕开动态规划，分支定界等优化方法