数学建模社区-数学中国
标题:
【源码】GA算法求解经典背包问题
[打印本页]
作者:
qq_1537237806
时间:
2021-1-1 09:08
标题:
【源码】GA算法求解经典背包问题
背包问题(Knapsack problem)是一种组合优化的
NP完全问题
。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,
计算复杂性理论
、密码学和应用数学等领域中。也可以将背包问题描述为
决定性问题
,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。
5 b+ w& I( }/ O8 e4 |' @1 h
4 V) `) ]- q; L+ R% [9 p; M6 |" j6 n
1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。
[3]
- ]; S% w( A$ F6 D5 ^: r. M8 ^! d
背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料,
[4]
选择投资和投资组合,
[5]
选择资产支持资产证券化
[6]
,和生成密钥为Merkle-Hellman
[7]
和其他背包密码系统。
$ A7 Y0 U$ c @, Y# E# q% Y
背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。
[8]
_# i% `' E( |5 ~0 Y
, ?. Y: M. i0 n7 S; w" s+ u# n
8 p* B- G6 Q" \( Y. T9 D
8 r" X" d5 w+ C8 \& A4 C: c1 h2 h( Y
knapsack_all.zip
2020-12-28 09:44 上传
点击文件名下载附件
下载积分: 体力 -2 点
2.34 KB, 下载次数: 2, 下载积分: 体力 -2 点
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5