请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4857|回复: 0

[代码资源] 【源码】GA算法求解经典背包问题

[复制链接]
字体大小: 正常 放大

473

主题

5

听众

1539

积分

  • TA的每日心情

    2021-1-13 09:31
  • 签到天数: 8 天

    [LV.3]偶尔看看II

    发表于 2021-1-1 09:08 |显示全部楼层
    |招呼Ta 关注Ta
    背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。
    0 Y  l! R7 w6 s- r6 ]+ ~
    & \) e% C2 H% c$ `1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。 [3]% Z! t& h% W) G. ]# m
    背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, [4] 选择投资和投资组合, [5] 选择资产支持资产证券化 [6] ,和生成密钥为Merkle-Hellman [7] 和其他背包密码系统。$ D7 U- y5 a3 k# ?+ w
    背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。 [8]
    0 A, b+ Z1 ^1 K
    $ z$ i6 H' H( _+ k* n& A: q$ x! K0 @  U/ Z9 Z4 w" ], z
    " g* T' e6 g* d0 ], L

    knapsack_all.zip

    2.34 KB, 下载次数: 2, 下载积分: 体力 -2 点

    zan
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-29 06:51 , Processed in 0.322917 second(s), 53 queries .

    回顶部