`
- 浏览:
38335 次
- 性别:
- 来自:
杭州
-
1. 背包问题.设有一个背包可以放入物品的重量为s,现在n件物品,重量分别为w[0],w[1]......w[n-1].问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之和正好等于s. 如果存在一种符合上述要求的选择,则称此背包问题有解;否则称此背包问题无解. 试用分而治之的算法设计求解背包问题的函数
转载自
http://blog.csdn.net/dongliheng/article/details/1569742
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
0-1背包问题算例
关于背包问题的源代码,包括贪心算法和动态算法
本例采用java实现的0-1背包问题,采用的是回溯法,参考算法设计与分析(第二版)
基于双子群协同进化思想和果蝇优化算法,...通过对多个0-1背包问题的算例进行测试,并将测试结果与其他文献结果进行比较,结果表明,双子群果蝇优化算法具有较好的全局寻优能力,可作为求解0-1背包问题的一种实用方法。
输入: 多个测例,每个测例的输入占三行。第一行两个整数:n(n)和c,第二行n个整数分别是w1...每个测例的输出占一行,输出一个整数,即最佳装载的总价值。 输入样例: 1 2 1 1 2 3 2 2 3 4 0 0 输出样例: 1 4
第一讲01背包问题 第二讲完全背包问题 第三讲多重背包问题 第四讲混合三种背包问题 第五讲二维费用的背包问题 第六讲分组的背包问题 第七讲有依赖的背包问题 第八讲泛化物品 第九讲背包问题问法的变化 附: USACO中...
描述: 需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi...每个测例的输出占一行,输出一个整数,即最佳装载的总价值。 输入样例: 1 2 1 1 2 3 2 2 3 4 0 0 输出样例: 1 4
最近两年比较流行的量子进化算法(QEA),能够求解一般的优化问题。算例是一个典型的背包问题(离散二值问题)。
使用matlab实现的蚁群算法,解决0 1背包问题为例解决组合优化问题
多选择背包问题是组合优化中的NP难题之一,采用一种新的智能优化算法——人工蜂群算法进行求解。该算法通过雇佣蜂、跟随蜂和侦察蜂的局部寻优来实现全局最优。基于算法实现的核心思想,用MATLAB编程实现,对参考文献...
0-1背包问题是典型的NP难问题,针对0-1背包问题提出分布估计算法(EDA)与遗传算法(GA)相结合的算法(E-GA)。该算法在每一次迭代中由二者共同产生种群,并行搜索,两种方法产生的个体数目动态变化,将EDA的全局...
基于双子群协同进化思想和果蝇优化算法,...通过对多个0-1背包问题的算例进行测试,并将测试结果与其他文献结果进行比较,结果表明,双子群果蝇优化算法具有较好的全局寻优能力,可作为求解0-1背包问题的一种实用方法。
背包的问题是,你有一个“袋子”,可以装有限数量的物品,鉴于你有一组物品可以从每个物品中选择,每个物品都有各自的“价值”,你如何才能最大限度地只装最有价值的物品呢。 让我们以现实世界为例。一个强盗闯入...
将粒子群算法与贪心思想相融合,提出一种用于求解0/1背包问题的更贪心混合粒子群算法。对超过背包重量约束的粒子的处理措施是去掉已经装进去且性价比最差的物品,直至满足重量约束为止,这种思想在改善粒子质量的...
描述: 需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi...每个测例的输出占一行,输出一个整数,即最佳装载的总价值。 输入样例: 1 2 1 1 2 3 2 2 3 4 0 0 输出样例: 1 4
0-1背包问题是一例典型的组合优化的NP完全问题。问题可以描述为:给定一组共n个物品,每种物品都有自己的重量wi, i=1~n和价值vi, i=1~n,在限定的总重量(背包的容量C)内,如何选择才能使得选择物品的总价值之和...
针对多维背包问题(MKP) NP-hard、约束强的特点, 提出一种高效的蚁群-拉格朗日松弛(LR) 混合优化算法. 该算法以蚁群优化(ACO) 为基本框架, 并基于LR 对偶信息定义了一种MKP效用指标. ACO使得整体算法具有全局搜索能力...
0 1背包问题是一例典型的组合优化的NP完全问题 问题可以描述为:给定一组共n个物品 每种物品都有自己的重量wi i 1 n和价值vi i 1 n 在限定的总重量(背包的容量C)内 如何选择才能使得选择物品的总价值之和最高 选择...
实例22 0-1背包问题 69 实例23 阶梯计数问题 72 实例24 二叉树算法集 74 实例25 模拟LRU页面置换算法 79 实例26 大整数阶乘新思路 82 实例27 银行事件驱动模拟程序 84 实例28 模拟迷宫探路 87 ...
以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号...