# 算法设计实验

**Repository Path**: zhangchenshuai1/algorithm-design-experiment

## Basic Information

- **Project Name**: 算法设计实验
- **Description**: No description available
- **Primary Language**: C++
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-05-18
- **Last Updated**: 2026-06-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 代码文件说明 

## tools.cpp

提供工具函数，包括：从文件中读数据，比较两个`vector<int>`是否相等等；

```c++
//函数原型
bool read_c(string filepath, int& ans);
bool read_w(string filepath, vector<int>& ans);
bool read_p(string filepath, vector<int>& ans);
bool read_s(string filepath, vector<int>& ans);
bool int_vector_compare(vector<int>&v1, vector<int>&v2);
```


## header.h

引入通用头文件，声明工具函数，定义背包问题数据结构；

```C++
//背包问题数据结构;
struct Back
{
    int c;              //capacity;
    vector<int>w;       //weight;
    vector<int>p;       //value;
    vector<int>s;       //standard selection (答案);
    vector<int>ans;     //ans (算法求出来的结果);
};
```


## dp-knapsack.cpp

功能：动态规划求解0/1背包；

输入：从`data/Knapsack-FSU-p01/`等文件夹中读取容量c、重量w、价值p、标准答案s；

输出：最优值、耗时、内存占用、填表数、状态转移次数，写入`experiments/dp-FSU-p01-08.txt`；

核心算法：迭代填表法。用`f[i][j]`表示考虑物品i到n、容量为j时的最大利润。初始化`f[n][j]`后自底向上填表，最后回溯得到最优解。


## bt-knapsack.cpp

功能：回溯法求解0/1背包；

输入：从`data/Knapsack-FSU-p01/`等文件夹中读取容量c、重量w、价值p、标准答案s；

输出：最优值、耗时、内存占用、搜索节点数、剪枝次数，写入`experiments/bt-FSU-p01-08.txt`；

核心算法：先将物品按p/w降序排列，采用深度优先搜索。限界条件使用紧限界（对剩余物品求解分数背包），当`cp + bound <= bestp`时剪枝。


## bb-knapsack.cpp

功能：分支限界法求解0/1背包；

输入：从`data/Knapsack-FSU-p01/`等文件夹中读取容量c、重量w、价值p、标准答案s；

输出：最优值、耗时、内存占用、搜索节点数、剪枝次数，写入`experiments/bb-FSU-p01-08.txt`；

核心算法：先将物品按p/w降序排列，采用优先队列实现最佳优先搜索。每个结点存储当前利润cp、重量cw及基于分数背包的紧限界上界，优先展开上界最高的结点。当结点上界`cp + bound <= bestp`时剪枝。


## greedy-knapsack.cpp

功能：贪心算法求解0/1背包（近似解）；

输入：从`data/Knapsack-FSU-p01/`等文件夹中读取容量c、重量w、价值p、标准答案s；

输出：近似最优值、耗时、内存占用、选择物品数、近似率，写入`experiments/greedy-FSU-p01-08.txt`；

核心算法：将物品按单位价值(p/w)降序排列，依次选择能装入背包的物品。注意：贪心法对0/1背包问题只能得到近似解，无法保证最优性（分数背包问题才能得到最优解）。近似率 = 贪心解 / 最优解 × 100%，用于衡量贪心算法的质量。



# 数据文件说明

数据来源: Florida State University (FSU)，共计8个数据集。

文件命名格式: `Knapsack-FSU-pXX/Knapsack-FSU-pXX_type.txt`，其中`XX`为01~08的实例编号，`type`为文件类型。

| 文件夹 | 类型 | 内容 | 格式 |
|--------|------|------|------|
| Knapsack-FSU-pXX/ | `_c.txt` | 背包容量C | 单个整数 |
| Knapsack-FSU-pXX/ | `_w.txt` | 物品重量 | 每行一个整数，共n行 |
| Knapsack-FSU-pXX/ | `_p.txt` | 物品价值 | 每行一个整数，共n行 |
| Knapsack-FSU-pXX/ | `_s.txt` | 最优解 (0/1) | 每行0或1，共n行，1表示装入 |

各数据集规模参数:

| 实例 | 物品数n | 容量C |
|------|---------|-------|
| p01 | 10 | 165 |
| p02 | 5 | 26 |
| p03 | 6 | 190 |
| p04 | 7 | 50 |
| p05 | 8 | 104 |
| p06 | 7 | 170 |
| p07 | 15 | 750 |
| p08 | 24 | 6,404,180 |



# 结果文件说明 

所有结果文件均位于`experiments/`目录下，采用固定列宽格式，数值保留2位小数，列间以空格分隔。

| 结果文件 | 对应程序 | 核心函数 | 列名 |
|----------|----------|----------|------|
| `dp-FSU-p01-08.txt` | dp-knapsack | `main()` 中的DP迭代 | 实例, 算法, n, 容量C, 最优值, 耗时(ms), 内存(KB), 填表数, 转移次数, 正确性 |
| `bt-FSU-p01-08.txt` | bt-knapsack | `backtrack()`, `tight_bound()` | 实例, 算法, n, 容量C, 最优值, 耗时(ms), 内存(KB), 搜索节点数, 剪枝次数, 正确性 |
| `bb-FSU-p01-08.txt` | bb-knapsack | `tight_bound()` + B&B主循环 | 实例, 算法, n, 容量C, 最优值, 耗时(ms), 内存(KB), 搜索节点数, 剪枝次数, 正确性 |
| `greedy-FSU-p01-08.txt` | greedy-knapsack | `main()` 中的贪心选择 | 实例, 算法, n, 容量C, 近似最优值, 耗时(ms), 内存(KB), 选择物品数, 近似率(%), 正确性 |

各列含义:

- **实例**: 数据集编号 (p01-p08)
- **算法**: DP=动态规划, BT=回溯法, BB=分支限界, Greedy=贪心算法
- **n**: 物品数量
- **容量C**: 背包容量
- **最优值**: 算法求得的最大总价值（贪心法为近似最优值）
- **耗时(ms)**: 核心算法部分的运行时间 (不含数据读取和结果写入)
- **内存(KB)**: 算法运行期间占用的内存估算值
- **填表数** (仅DP): DP表实际填充的单元格数
- **转移次数** (仅DP): 发生状态转移（比较并取max）的格子数
- **搜索节点数** (BT/BB): 搜索树中访问的结点总数
- **剪枝次数** (BT/BB): 限界条件触发而剪掉的结点/分支数
- **选择物品数** (仅Greedy): 贪心算法选择的物品数量
- **近似率(%)** (仅Greedy): 贪心解与最优解的比值 × 100%，衡量贪心算法的质量。100%表示得到最优解，越低表示与最优解差距越大
- **正确性**: OK表示算法结果与标准答案一致，ERROR表示不一致（贪心法通常为ERROR，这是正常现象）

编译与运行: 项目根目录下执行`make`编译所有程序，可执行文件生成于项目根目录（Windows下带`.exe`后缀），以`./<程序名>`直接运行（Linux下）。