免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 4452 | 回复: 14

[算法] 01背包问题如何求得最佳取法,而不仅是最大价值。 [复制链接]

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-28 20:45 来自手机 |显示全部楼层
01背包问题如何求得最佳取法,而不仅是最大价值。
兄弟不才,只知道最大值,而不知如何取。

论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2014-08-28 21:03 |显示全部楼层
整数规划基本上就是个恶梦。

这个问题,我虽然没有仔细研究过,但是我感觉对于大规模问题来说,没有什么好算法去找全局最优解,有个满意解也就了。

而且实际当中的很多问题就是直接求满意解的,至少比没有解好。

小规模的,怎么都好说,关键是大规模的。

很多专业的计算软件都对整数规划没办法,因为缺乏对应的理论工具。

就是是一般的无约束的非线的非凸规划,也没啥办法。

什么多下降类算法,多初始点的下降类算法、群类算法、都没有办法保证理论上的全局最优。。。

论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2014-08-28 21:05 |显示全部楼层
有个算法叫分支定界法,比较有意思,你可以去玩玩。。。

论坛徽章:
1
2015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2014-08-29 00:48 |显示全部楼层
最佳如何定义?

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2014-08-29 08:45 |显示全部楼层
回复 2# fender0107401


    我以后有空给你发个double规划的, 用callback的返回值来界定最佳值。
根据callback(如为null, 有default的callback)不同, 可以找到小于目标的最佳值, 大于目标的最佳值, 和目标值最接近的最佳值(绝对值);
如果找到的最佳值相等, 选择数目最小的那个组合;

当然, 这种算法要找的值为“最佳”, 那只能是遍历。


论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2014-08-29 09:51 |显示全部楼层
回复 5# folklore

哈哈。

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2014-08-29 10:32 |显示全部楼层
各位大神都太注重算法了

游戏这种项目,背包容量是分阶段扩展的,物品种类也就那些种,一般情况,数量级不是很大

对于可能存在的各种物品最大数量,事先算出各种容量小于背包容量的组合,按value从大到小存在数组并配在文件里,[1] = "A5B3C4", [2] = "A5B3C3"

根据目前的背包容量,在配置文件里读出所有可能的组合数组,遍历看当前物品能否满足,比如"A5B3C4",看当前已有物品是否足够5个A3个B4个C,够的话就用"A5B3C4",否则找下一个稍小的value数组

论坛徽章:
35
双子座
日期:2014-05-09 17:56:38程序设计版块每日发帖之星
日期:2015-08-30 06:20:00程序设计版块每日发帖之星
日期:2015-12-24 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-27 11:07:07程序设计版块每日发帖之星
日期:2016-01-12 06:20:0015-16赛季CBA联赛之北京
日期:2016-01-15 01:01:2115-16赛季CBA联赛之浙江
日期:2016-01-15 22:38:20程序设计版块每日发帖之星
日期:2016-01-18 06:20:00每日论坛发贴之星
日期:2016-01-18 06:20:0015-16赛季CBA联赛之北控
日期:2016-01-30 21:43:01程序设计版块每日发帖之星
日期:2016-02-08 06:20:0015-16赛季CBA联赛之山西
日期:2016-02-20 10:54:41
发表于 2014-08-29 11:12 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-29 11:16 |显示全部楼层
没关系,都可以转换为01背包。只有东西不是无限多就行了。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-08-29 11:18 |显示全部楼层
我看了一篇博客上有01背包的详细解法。要知道具体选法要N*V的空间?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP