# 01_knapsack **Repository Path**: ibenzene/knapsack_01 ## Basic Information - **Project Name**: 01_knapsack - **Description**: 使用动态规划、回溯及分支限界三种算法求解01背包问题。 - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: template - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2021-11-26 - **Last Updated**: 2023-05-20 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 01背包问题的求解 ## 项目概述 本项目是针对TJUCIC开设的《算法设计与分析》课程结业实验的验收性作业项目. 项目内容是针对01背包问题，利用动态规划、回溯及分支限界三种算法进行求解，目的在于探究不同算法解决同一问题的复杂度，归纳不同求解算法的优缺点. ## 文件结构 ``` ├── include # 存储全局使用的头文件 │   ├── common.h # 公用的头文件 │   ├── 01_knapsack.h # 核心类的定义 │   ├── misc.h # 杂项 │   ├── 01_knapsack.inl # 核心类的显式实例化 │   └── misc.inl # 其它模板类的显示实例化 ├── input # 测试样例 │   ├── instances_01_KP_FSU # 一般规模数据集 │   ├── large-scale_UU # 大规模数据集 │   └── low-dimensional_UU # 小规模数据集 ├── Makefile # 提供工程的构建、运行、测试等功能 ├── src # 源文件 │   ├── 01_knapsack.cpp # 核心类方法的定义 │   ├── main.cpp # 主程序入口 │   ├── misc.cpp # 杂项 │   └── special.cpp # 浮点相关 ├── driver.py # 驱动脚本 └── test.sh # 测试脚本 ``` ## 快速开始 开始前需注意，本程序不支持Windows x86/64系统，在运行前请务必确保你的操作系统使用的是Linux内核，此外还需检查你的Python版本是否为3.6.0以上： > python3 --version ### 构建项目 > make ### 测试全部数据集 > make run ## 高级操作 ### 测试指定数据集 > make test ### 查看错误日志 > cat output/[filename][-algorithm].log ### 清除输出文件 > make clean ### 修改指定数据集 你可以通过修改`./Makefile`文件中变量`testcase_BIN`的值来运行你想测试的数据集. ### 超时控制 你可以在驱动脚本`driver.py`中更改`time_limit`的值来控制自动化测试的时间，超过该时长将直接跳过正在处理的数据集，默认最大等待时间为`2m`. ### 添加数据集 如果想要测试额外的数据集，请将其以目录的形式放在`input/`目录下，并在驱动脚本`driver.py`中的`mode`和`strategy`字典中设置相应参数. ## 参数说明 运行程序需指定运行的算法和模式，目前该项目只实现了动态规划、回溯及分支限界三种基本算法，需在`driver.py`中的`strategy`中设置，算法对应参数值如下 - 动态规划: 0 - 回溯法： 1 - 分支限界法： 2 我们为测试数据提供了三种可选模式，你需要根据样本需求来选择相应的模式，三种模式分别为 - 值模式：样本要求只验证结果，即最大收益值,该模式对应的参数值为0 - 向量模式：样本要求只验证解向量，该模式对应的参数值为1 - 混合模式：样本既需要验证结果，有需要验证解向量，该模式对应的参数值为2 需要注意的是，由于该实验程序在运行过程中不保存所有的最优解，因此混合模式可能会出现解向量失配的情况，你可以在实验日志中看到详细信息，这是因为一个最优解可能会对应多个解向量，所以不建议以混合模式来测试数据集，但可以担保的是，最优值一定是匹配的.