马尔可夫链蒙特卡洛-0/1背包问题
该资料库引用了该学科的最终：《蒙特卡洛算法和马尔可夫链中的特殊主题》 ，PESC / COPPE / UFRJ ，由 教授在2018年第一学期教授。
学生们：
关于
该存储库的目的是为0/1背包问题建立解决方案，也就是说，每个元素都可以或不可以不经过重复就出现在解决方案中。 开发的代码旨在评估涉及Markov Chains Monte Carlo的不同算法的结果和性能。 与伪多项式求解算法和贪婪算法（称为“爬山”）相比，本文涵盖的技术涉及不同冷却和过渡策略下的随机游走，Metropolis Hastings，模拟退火算法。 此外，该存储库还试图提出可能的场景，在这些场景中，马尔可夫链蒙特卡洛算法比确定性算法更具优势。
运行算法
所有算法都是使用编写的，并且在src目录中可用。 在data目录中，您可以找到一些可以由算法执行的问题。
涉及Mark
2021-10-26 11:34:53
129KB
1
用遗传算法实现二进制背包问题。
求解器的输入（KnapSackGA.java）是一个名为init.txt的文件，该文件的每一行包含以下内容：
项目数（例如7）
每个项目的值（以空格分隔）（例如1 2 3 4 5 6 7）
每个项目的重量（以空格分隔）（例如14 11 10 13 12 9 8）
背包最大尺寸（例如70）
人口规模（例如50）
世代数（例如100）
交叉概率（例如0.6）
突变概率（例如0.015）
2021-05-02 22:03:15
4KB
1
背包问题近似算法PTAS和FPTAS. The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS). 作者: Katherine Lai, Prof. M. X. Goemans
2021-02-23 10:21:11
93KB
1