# 01knapsack-tests

**Repository Path**: ysq233/01knapsack-tests

## Basic Information

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

## Statistics

- **Stars**: 2
- **Forks**: 1
- **Created**: 2025-05-14
- **Last Updated**: 2025-06-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


# 算法课程设计：0/1背包问题的算法测试和分析
## 项目概述
## UU(Unicauca University)数据集使用指南
### 概述

我们已经成功将UU数据集格式转换为适合 `run_tests.py` 使用的标准格式。

 转换前（原始UU格式）：
```
data/
├── low-dimensional/          # 小规模数据
│   ├── f1_l-d_kp_10_269
│   ├── f2_l-d_kp_20_878
│   └── ...
├── large_scale/             # 大规模数据
│   ├── knapPI_1_100_1000_1
│   ├── knapPI_2_100_1000_1
│   └── ...
├── low-dimensional-optimum/ # 小规模最优解
└── large_scale-optimum/     # 大规模最优解
```
转换后（标准格式）：
```
data_converted/
├── f1_l-d_kp_10_269/
│   └── test.in
├── f2_l-d_kp_20_878/
│   └── test.in
├── knapPI_1_100_1000_1/
│   └── test.in
├── ...
└── optima/
    └── optima.txt           # 汇总的最优解文件
```

### 数据集信息

- **小规模数据集**: 10个文件 (f1 到 f10)
- **大规模数据集**: 21个文件 (knapPI系列)
- **总计**: 31个测试用例
- **最优解**: 所有31个测试用例都有已知最优解

### 使用方法

#### 1. 使用转换后的测试脚本
```bash
cd src/
python3 run_tests_for_converted_data.py [算法名]
```

例如：
```bash
python3 run_tests_for_converted_data.py greedy
python3 run_tests_for_converted_data.py dp
python3 run_tests_for_converted_data.py bt
python3 run_tests_for_converted_data.py bb
```

#### 2. 算法程序要求
- 算法程序应命名为 `{算法名}_01knapsack.cpp`
- 程序应接受一个命令行参数：数据集名称
- 程序从标准输入读取数据，格式为UU标准格式：
  ```
  n capacity
  value1 weight1
  value2 weight2
  ...
  ```
- 程序输出格式：`数据集名称,结果值`

#### 3. 输出文件
运行测试后会生成：
- `../experiments/{算法名}_01knapsack-01.txt` - 详细测试结果
- `../experiments/{算法名}_01knapsack-01-accuracy.txt` - 准确率汇总
- `../experiments/{算法名}_01knapsack-01-performance.txt` - 性能测试结果

### 数据集特点

#### 小规模数据集 (f系列)
- 规模: 4-23个物品
- 容量: 11-10000
- 适合测试算法正确性

#### 大规模数据集 (knapPI系列)
- 规模: 100-10000个物品
- 容量: 固定1000
- 适合测试算法性能和可扩展性

### 转换脚本

如需重新转换或转换其他UU数据集：

1. **数据集结构转换**:
   ```bash
   python3 convert_dataset_structure.py
   ```

2. **最优解文件生成**:
   ```bash
   python3 create_optima_file.py
   ```

### 注意事项

- 确保C++算法程序已编译
- 数据集路径使用相对路径 `../data_converted`
- 最优解文件路径 `../data_converted/optima/optima.txt`
- 所有输出文件保存在 `../experiments/` 目录下 

## JJ(JorikJooken)数据集使用指南
### 概述
```
.
|── optima
|    ├── optima.csv
|    └── optima.txt
├── n_1000_c_1000000_g_10_f_0.1_eps_0_s_100
│   ├── outp.out
│   ├── test.in
│   └── time.out
├── n_1000_c_1000000_g_10_f_0.1_eps_0_s_200
│   ├── outp.out
│   ├── test.in
│   └── time.out
├── n_1000_c_1000000_g_10_f_0.1_eps_0_s_300
│   ├── outp.out
│   ├── test.in
│   └── time.out
├── n_1000_c_1000000_g_10_f_0.1_eps_0.0001_s_100
│   ├── outp.out
│   ├── test.in
│   └── time.out
```
- 共3240组数据
- optima/optima.txt中储存着每组数据的最优解
- 均为大规模数据，n从400到1200不等，c在1000000及以上
### 使用数据集
进入src/JJ-src目录
```bash
cd src/JJ-src
```
调用测试脚本，自动编译所有.cpp文件，并测试在命令行指定的算法
```bash
python3 run_tests.py [算法名,如greedy]
```
测试结果自动写入 experiments/JJ-experiments
```
.
├── bb_01knapsack-01-accuracy.txt
├── bb_01knapsack-01-performance.txt
├── bb_01knapsack-01.txt
├── bt_01knapsack-01-accuracy.txt
├── bt_01knapsack-01-performance.txt
├── bt_01knapsack-01.txt
├── dp_01knapsack-01-accuracy.txt
├── dp_01knapsack-01-performance.txt
├── dp_01knapsack-01.txt
├── greedy_01knapsack-01-accuracy.txt
├── greedy_01knapsack-01-diff-ignore-1.txt
├── greedy_01knapsack-01-diff.txt
├── greedy_01knapsack-01-performance.txt
└── greedy_01knapsack-01.txt
```
运行测试后会生成：
- `../experiments/{算法名}_01knapsack-01.txt` 
   - 详细测试结果
- `../experiments/{算法名}_01knapsack-01-accuracy.txt` 
   -  准确率汇总
- `../experiments/{算法名_01knapsack-01-performance.txt`
   - 性能测试结果

此外，我们可以测试解的误差大小
运行
```bash
python3 diff.py
```
生成
- 每组数据的误差结果
- 所有数据的平均误差结果
> 把无解视为100%误差

如果我们想忽视无解情况，可以添加参数
```bash
python3 diff.py --ignore-1
```
输出忽视无解情况的误差结果
## FSU(Florida State University)数据集使用指南
### 概述
### 使用数据集