算法设计与分析/数据结构与算法实验6:0-1背包问题(回溯法)

简介: 算法设计与分析/数据结构与算法实验6:0-1背包问题(回溯法)

1.实验目的

(1)掌握回溯法的处理思路与算法框架。

(2)掌握应用回溯法解决具体问题的方法。

(3)掌握回溯法的广泛应用。

2.实验内容

(1)问题描述

image.png


要求使用回溯法解决该问题。

(2)输入

image.png


(3)输出

image.png


3.问题实例分析

image.png


因此,先装入第一个物品,此时体积足够装入第二个物品。装完第二个物品后,还能在装第三个物品。以深度优先的顺序,此时访问到的解空间树的结点如图所示:

注意:我自己都觉得图太丑了,大家画图时不要为了方便用wps自带的画图工具画!!!还是visio好!!!

image.png

image.png


从该结点回溯到上一结点,并在访问右子树前分别计算每个结点的当前价值cp与剩余价值r,发现都可以将右子树直接剪枝剪掉。

image.png

image.png

image.png


4.算法描述及说明

正如第3节问题实例分析所述,算法的整体流程如下:

1.输入数据,并对每个物品进行编号。

2.计算每个物品的单位价值,并将物品按单位价值排序。

3.对于第i ii个物品,判断剩余体积是否能够装下该物品。

4.若能装下该物品,则将该物品装入,并构造相应结点。

5.若不能装入该物品,则不将该物品装入,考虑下一物品。

6.在第4步中的物品撤出背包,构造相应结点,并计算剩余物品能产生价值的上界。若上界大于当前最优解,则装入考虑下一物品,否则不考虑。

7.重复3-6的步骤,直到所有物品都被考虑过。

5.算法正确性分析

算法会正确地结束:在遍历完解空间后,找到了使总价值最大的解,算法会停止。

回溯法的正确性分析:开始时,根结点是解空间树唯一的活结点,也是当前的扩展结点。在这个扩展结点处,搜索向深度方向移至一个新节点。这个新结点成为新的扩展结点。如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点成为死结点。应回溯至最近的活结点处,使得这个活结点成为当前扩展结点。回溯法以系统的方式递归地在解空间树中进行搜索,直到找到所要求的解惑解空间中已无活结点。

因此,利用回溯法会系统地查找背包问题的所有可行解,在剪枝时利用限界函数与剪枝函数剪去了不可行的分支,保留了可行并能产生最大解的分支。

从而,该算法是正确的。

6.算法时间复杂性分析

image.png

7.运行结果展示及其说明

image.png

8.心得体会

9.程序源代码

#include<iostream>
#include<algorithm>
using namespace std;
double cw;//当前重量
double cp;//当前价值
double bestp;//当前最优价值
int n;//物品数量
double c;//背包容量
const int N = 105;
int x[N];
struct Bag {
  double w, v;
  int id, x;
};
Bag bag[N];
bool cmp(Bag a, Bag b) {
  return (a.v / a.w) > (b.v / b.w);
}
double bound(int i) {
  double cleft = c - cw;
  double bd = cp;
  while (i <= n && bag[i].w <= cleft) {
    cleft -= bag[i].w;
    bd += bag[i].v;
    i++;
  }
  if (i <= n)
    bd += bag[i].v * cleft / bag[i].w;
  return bd;
}
void dfs(int i) {
  if (i > n) {
    bestp = cp;
    for (int i = 1; i <= n; i++) 
        x[bag[i].id] = bag[i].x;
    return;
  }
  if (cw + bag[i].w <= c) {
    cw += bag[i].w;
    cp += bag[i].v;
    bag[i].x = 1;
    dfs(i + 1);
    cw -= bag[i].w;
    cp -= bag[i].v;
    bag[i].x = 0;
  }
  if (bound(i + 1) > bestp)
    dfs(i + 1);
}
int main() {
  cin >> n >> c;
  for (int i = 1; i <= n; i++)
    cin >> bag[i].w;
  for (int i = 1; i <= n; i++)
    cin >> bag[i].v;
  for (int i = 1; i <= n; i++)
    bag[i].id = i;
  sort(bag + 1, bag + 1 + n, cmp);
  dfs(1);
  cout << bestp<<endl;
  for (int i = 1; i <= n; i++)
    cout << x[i] << " ";
  return 0;
}


目录
相关文章
|
21天前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
45 4
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
49 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
19天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
18 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
4天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
12天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
28 4
|
18天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
63 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
19天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
13 0
数据结构与算法学习十四:常用排序算法总结和对比
|
19天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
26 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
10天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
20 0
|
16天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
22 0