1
实验名称
实验 7 0-1 背包问题的回溯算法实现
实验日期
2021.6.15-6.16
实验地点
J13-332
指导老师
王路
实验成绩
一、实验目的和要求：
1. 学习并掌握回溯法
2. 利用迭代回溯和递归回溯两种方法解决 01 背包问题。
二、实验环境：
Vs2019--c++实现
三、算法描述及实验步骤
1.问题描述：
0-1 背包问题：我们有 n 种物品，物品 j 的重量为 wj，价格为 pj。我们假定所有物品的重量
和价格都是非负的。背包所能承受的最大重量为 c。如果限定每种物品只能选择 0 个或 1
个，则问题称为 0-1 背包问题。计算出背包能承受的最大价值量。
在 本 次 试 验 中 ， 使 用 到 的 实 例 为 ：
n=7，c=150，w={35,30,60,50,40,10,25}，p={10,40,30,50,35,40,30}.
2.算法设计
回溯法在包含问题的所有解的解空间树中按照深度优先的策略，确定了解空间的组织结构
后，回溯法从开始节点出发，以深度优先方式搜索整个解空间，这个开始节点成为活节点，
- 1
- 2
- 3
- 4
- 5
前往页