# algorithm

**Repository Path**: fenling18/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2025-05-31
- **Last Updated**: 2025-06-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

 # 代码文件说明
数据输入格式：输入目标文件夹，目的文件夹，结果输出到目标文件夹下以样例文件为名的文件夹内，outp.out为结果,time.out为计算时间
bt_Knapsack_problem.java（回溯算法）
dp_Knapsack_problem.java（动态规划算法）
ga_Knapsack_problem.cpp（贪心算法）


 # 数据文件说明
问题实例文件。首行为物品数量n。随后n行描述每个物品，包含三个整数：物品ID、物品收益、物品重量。末行为背包容量c。
示例内容：
"
3
0 3 8
1 2 8
2 9 1
10
"
表示包含3个物品的实例，背包容量为10。ID为1的物品收益3重量8，ID为2的物品收益2重量8，ID为3的物品收益9重量1。

以下数据来自artemisa.unicauca.edu.co
文件名： kp_n_wmax
kp：0/1 背包问题实例名称
n：项数
wmax：背负式行李箱容量
 knapPI_1_200_1000_1
 knapPI_2_100_1000_1
 knapPI_2_200_1000_1
 knapPI_3_100_1000_1
 knapPI_3_200_1000_1
 f10_l-d_kp_20_879
 f1_l-d_kp_10_269
 f2_l-d_kp_20_878
 f3_l-d_kp_4_20
 f4_l-d_kp_4_11
 f6_l-d_kp_10_60
 f7_l-d_kp_7_50
 f8_l-d_kp_23_10000
 f9_l-d_kp_5_80

以下数据来自github，文件名由6个参数构成为n,c,g,f,eps,s
​​n​​
​​含义​​：物品数量（Number of items）
​​作用​​：决定生成的背包问题实例中包含多少个物品。
​​c​​
​​含义​​：背包容量（Knapsack capacity）
​​作用​​：设定背包的最大承重限制。
​​g​​
​​含义​​：生成器模式（Generator mode）
​​作用​​：控制生成物品收益（profit）和重量（weight）的方式。论文中可能定义了不同的模式（如随机分布、特定结构等），但具体模式需参考源代码或论文细节。
​​f​​
​​含义​​：权重因子（Weight factor）
​​作用​​：影响物品重量的生成规则，可能与物品收益的关联性有关（例如强相关、弱相关或无关实例）。
​​eps
​​含义​​：扰动系数（Perturbation parameter）
​​作用​​：在生成过程中引入随机扰动，可能用于调整问题实例的难度或多样性。
​​s​​
​​含义​​：随机种子（Random seed）
​​作用​​：确保生成的实例可复现。相同参数和种子会生成完全相同的实例。
n_400_c_1000000_g_2_f_0.1_eps_0.0001_s_100
n_400_c_1000000_g_2_f_0.1_eps_0.0001_s_200
n_400_c_1000000_g_2_f_0.1_eps_0.0001_s_300
n_400_c_1000000_g_2_f_0.1_eps_0.001_s_100
n_400_c_1000000_g_2_f_0.1_eps_0.001_s_200
n_400_c_1000000_g_2_f_0.1_eps_0.001_s_300
n_400_c_1000000_g_2_f_0.1_eps_0.01_s_100
n_400_c_1000000_g_2_f_0.1_eps_0.01_s_200
n_400_c_1000000_g_2_f_0.1_eps_0.01_s_300
n_400_c_1000000_g_2_f_0.1_eps_0.1_s_100
n_400_c_1000000_g_2_f_0.1_eps_0.1_s_200
n_400_c_1000000_g_2_f_0.1_eps_0.1_s_300
n_400_c_1000000_g_2_f_0.1_eps_0_s_100
n_400_c_1000000_g_2_f_0.1_eps_0_s_200
n_400_c_1000000_g_2_f_0.1_eps_0_s_300
n_400_c_1000000_g_2_f_0.1_eps_1e-05_s_100
n_400_c_1000000_g_2_f_0.1_eps_1e-05_s_200
n_400_c_1000000_g_2_f_0.1_eps_1e-05_s_300
n_400_c_1000000_g_2_f_0.2_eps_0.0001_s_100
n_400_c_1000000_g_2_f_0.2_eps_0.0001_s_200
n_400_c_1000000_g_2_f_0.2_eps_0.0001_s_300
n_400_c_1000000_g_2_f_0.2_eps_0.001_s_100
n_400_c_1000000_g_2_f_0.2_eps_0.001_s_200
n_400_c_1000000_g_2_f_0.2_eps_0.001_s_300

以下数据来自people.sc.fsu.edu,文件名表示例子编号
n1
n2
n3
n4
n5
n6
n7
n8

 # 结果文件说明
输出结果均放在experiments文件夹中，命名规则为 算法-数据来源
如dp-Knapsack_problem-people.sc.fsu.edu-02表示为动态规划算法计算Knapsack_problem-people.sc.fsu.edu-02数据集的结果

结果文件夹中每个样例的结果放在样例为名的文件夹中，包含两个文件为outp.out和time.out
outp.out - 算法求解该实例的输出结果。若求解成功，文件首行为选中物品总收益，后续每行列出一个选中物品的ID、收益和重量。
示例：
"
12 
1 3 8
2 9 1
"
表示最优解总收益12，由物品1收益3重量8和物品2收益9重量1的物品组成。