算法分析与设计实验报告

2023-09-25 05:16| 来源: 网络整理| 查看: 265

算法分析与设计实验报告——0-1背包问题的回溯算法实现

目录：算法分析与设计实验报告——0-1背包问题的回溯算法实现一、实验目的二、实验要求三、实验原理四、实验过程(步骤)五、运行结果六、实验分析与讨论七、实验特色与心得附件一实验过程(步骤)递归法非递归法附件二运行结果递归法非递归法

一、实验目的

掌握回溯法的基本思想和解决问题的基本步骤，认识回溯法和动态规划、贪心选择的联系与区别，对比解决同一问题的三种算法设计策略的优缺点。

二、实验要求

用c++语言实现递归回溯回溯和迭代回溯解决0-1背包问题，分析时间复杂性，体会回溯法解决问题的基本思路和步骤。

三、实验原理四、实验过程(步骤)

见附件一实验步骤、特点重要源代码（流操作的部分要醒目的提示并注释）

五、运行结果

见附件二

六、实验分析与讨论

遇到的问题，及解决方案

七、实验特色与心得附件一实验过程(步骤) 递归法 /* * Algorithm experiment 7 0-1背包问题的回溯算法递归实现 */ #include "bits/stdc++.h" #define maxn 10000 using namespace std; int mn[maxn] = {0}; int mnn[maxn] = {0}; int perw[maxn] = {0}; int maxw = 0; template class Knap { public: // friend Typep Knapsack(Typep *, Typew *, Typew, int); public: Typep Bound(int i); void Backtrack(int i); Typew c;//背包容量 int n;//物品数 Typew *w;//物品重量数组 Typep *p;//物品价值数组 Typew cw;//当前重量 Typep cp;//当前价值 Typep bestp;//当前最优价值 }; template void Knap::Backtrack(int i) { if (i > n) {//到达叶节点 bestp = cp; maxw = cw; memcpy(mnn, mn, (n + 1) * sizeof(int)); return; } if (cw + w[i] //进入右子树 mn[i] = 0; Backtrack(i + 1); } } template Typep Knap::Bound(int i) {//计算上界 Typew cleft = c - cw;//剩余容量 Typep b = cp; while (i public: // friend int Knapsack(int *, int *, int, int); public: int operator return a.operator Q[i - 1].ID = i; Q[i - 1].d = 1.0 * p[i] / w[i]; P += p[i]; W += w[i]; } if (W cout int c, n; cout n; cout c; int *w = new int[n]; cout printf("p[%d]：", i); cin >> p[i]; } int bestp = Knapsack(p, w, c, n); cout cout0}; int cnt[maxn] = {0}; int maxw = 0; template class Knap { public: // friend Typep Knapsack(Typep *, Typew *, Typew, int); public: Typep Bound(int i); void Backtrack(int i); Typew c;//背包容量 int n;//物品数 Typew *w;//物品重量数组 Typep *p;//物品价值数组 Typew cw;//当前重量 Typep cp;//当前价值 Typep bestp;//当前最优价值 }; template void Knap::Backtrack(int i) { while (i >= 1) { if (cnt[i] if (i > n) { bestp = cp; maxw = cw; memcpy(mnn, mn, (n + 1) * sizeof(int)); i--; } int child = 1 - cnt[i]; if (child) { if (cw + w[i] if (Bound(i + 1) > bestp) {//进入右子树 mn[i] = 0; cnt[i]++; i++; } else cnt[i]++; } } } else { cnt[i] = 0; i--; } } } template Typep Knap::Bound(int i) {//计算上界 Typew cleft = c - cw; Typep b = cp; while (i public: // friend int Knapsack(int *, int *, int, int); public: int operator return a.operator Q[i - 1].ID = i; Q[i - 1].d = 1.0 * p[i] / w[i]; P += p[i]; W += w[i]; } if (W cout int c, n; cout n; cout c; int *w = new int[n]; cout printf("p[%d]：", i); cin >> p[i]; } int bestp = Knapsack(p, w, c, n); cout cout

【本文地址】

公司简介

联系我们