算法实验报告01背包问题

河北工业大学计算机科学与软件学院 算法分析与设计实验算法分析与设计实验 报告报告 实验 0 1 背包问题 姓名 姓名 学号 学号 班级 班级 0 1 背包问题的动态规划算法背包问题的动态规划算法 一 一 实验目的与要求 实验目的与要求 熟悉 C C 语言的集成开发环境 通过本实验加深对贪心算法 动态规划和回溯算法的理解 二 二 实验内容 实验内容 掌握贪心算法 动态规划和回溯算法的概念和基本思想 分析并掌握 0 1 背包问题的 三种算法 并分析其优缺点 三 三 实验程序 实验程序 include stdio h int n 5 int w 0 3 2 1 4 5 int v 0 25 20 15 40 50 int x 5 int V 6 7 int C 6 void main void int i j for i 0 i n i V i 0 0 for j 0 j C j V 0 j 0 for i 1 i n i for j 1 j C j if jV i 1 j w i v i V i j V i 1 j else V i j V i 1 j w i v i 以上构造动态规划表 j C for i n i 0 i if V i j V i 1 j x i 1 j j w i else x i 0 printf 动态规划表如下 n for i 0 i 6 i for j 0 j 7 j printf 8d V i j printf n printf 装入背包物品 n for i 0 i 6 i printf 4d x i printf n 背包取得最大值 n printf 4d n V n C 三 实验结果 三 实验结果 四 实验分析 四 实验分析 这次实验用到的是动态规划法 0 1 背包问题用动态规划法首先要构造动态规划 表 用三个 for 语句实现 根据动态规划表每行的最大值变化确定每个元素的 装入与否 逐步确定出装入背包的物品 背包容量的最大值也就是动态规划表 最右下角 在本次实验中遇到了动态规划表构造紊乱的状况 经核查是因数组 的初始位置 0 混淆成 1 造成的 0 1 背包问题的贪心算法背包问题的贪心算法 一 一 实验目的与要求 实验目的与要求 熟悉 C C 语言的集成开发环境 通过本实验加深对贪心算法 动态规划和回溯算法的理解 二 二 实验内容 实验内容 掌握贪心算法 动态规划和回溯算法的概念和基本思想 分析并掌握 0 1 背包问题的 三种算法 并分析其优缺点 三 三 实验程序 实验程序 include stdio h void main void int C 6 背包容量 6 int n 5 5 个物品 int w 3 2 1 4 5 物品重量 int v 25 20 15 40 50 物品价值 int x 0 0 0 0 0 单位价值初始化 int q 5 int m i j p vx wx k ii int V 0 总价值初始化 计算单位价值 printf 单位价值为 n for m 0 m 5 m q m m x m v m w m printf x d d t m x m 冒泡排序 for i 0 i 4 i for j 0 j 4 i j if x j x j 1 交换单位价值 p x j x j x j 1 x j 1 p 交换价值对应位置 vx v j v j v j 1 v j 1 vx 交换重量对应位置 wx w j w j w j 1 w j 1 wx 交换商品编号 m q j q j q j 1 q j 1 m printf n 单位价值降序为 n for i 0 i 5 i printf x d d t i x i 装入背包 for i 0 i ni if w i C V v i C C w i k i if C 0 V v i C w i C 0 for ii 0 ii k ii printf n 放入第 d 个物品 n 物品的重量为 d n 物品的价值为 d n 背包 剩余容量为 d n q ii 1 w ii v ii C printf n 总价值为 d t V 四 四 实验结果 实验结果 五 五 实验分析 实验分析 本次实验是以贪心算法解决背包问题 贪心算法要求出每个本次实验是以贪心算法解决背包问题 贪心算法要求出每个 物品的单位价值 根据单位价值降序排列 再依次装入背包 物品的单位价值 根据单位价值降序排列 再依次装入背包 当最后一个物品不能完全装入时 装入部分使背包容量为当最后一个物品不能完全装入时 装入部分使背包容量为 0 在本次实验中 遇到几个难题 在本次实验中 遇到几个难题 1 保证物品按单位价值排列后依然能知道他的原始顺序位置 保证物品按单位价值排列后依然能知道他的原始顺序位置 经过几番思考 决定设置一个数组来保存该物品的原始经过几番思考 决定设置一个数组来保存该物品的原始 位置 在冒泡算法交换时同时交换物品编号 位置 在冒泡算法交换时同时交换物品编号 2 装入背包过程如何保证装入不完整物品 即背包剩余容量装入背包过程如何保证装入不完整物品 即背包剩余容量 不能满足完全放入下一个物品 不能满足完全放入下一个物品 通过本次试验又熟悉了冒泡算法的应用 以及多重通过本次试验又熟悉了冒泡算法的应用 以及多重 for 循环的循环的 应用 应用 0 1 背包问题的回溯算法背包问题的回溯算法 一 一 实验目的与要求 实验目的与要求 熟悉 C C 语言的集成开发环境 通过本实验加深对贪心算法 动态规划和回溯算法的理解 二 实验内容 实验内容 掌握贪心算法 动态规划和回溯算法的概念和基本思想 分析并掌握 0 1 背包问题的 三种算法 并分析其优缺点 三 三 实验程序 实验程序 include 定义 min max 函数 int min int a int b if a b return b else return a int max int a int b if a b return a else return b void Knapsack int v 6 int w 6 int c int n int m 6 6 int jmax min w n 1 c for int j 0 j jmax j m n j 0 for int p w n p1 i jmax min w i 1 c for int j 0 j jmax j m i j m i 1 j for int t w i t w 1 m 1 c max m 1 c m 2 c w 1 v 1 void Traceback int m 6 6 int w 6 int c int n int x 6 for int i 1 i n i if m i c m i 1 c x i 0 else x i 1 c w i x n m n c 0 1 0 void main int n1 5 int c1 6 int w1 6 0 3 2 1 4 5 int v1 6 0 25 20 15 40 50 int t 6 6 int x1 6 int m 0 cout 请输入背包的容量 c1 cout 0 1 背包如下 endl cout 物品的重量分别为 endl for int p 1 p 6 p cout w1 p cout endl cout 物品的价值分别为 endl for int q 1 q 6 q cout v1 q cout endl cout 背包的容量为 c1 endl cout 要选择的物品是 endl Knapsack v1 w1 c1 n1 t for int i 1 i n1 i cout v1 i endl Traceback t w1 c1 n1 x1 for i 1 i n1 i if x1 i 1 m v1 i cout 第 i 件物品 endl cout 最大总价值为 m endl 四 四 实验结果 实验结果 五 五 实验分析 实验分析 本次实验用回溯法解决本次实验用回溯法解决 0 1 背包问题 回溯法首先要建立背包问题 回溯法首先要建立 0 1