算法设计与分析/数据结构与算法实验7:0-1背包问题(分支限界法)

简介: 算法设计与分析/数据结构与算法实验7:0-1背包问题(分支限界法)

1.实验目的

 (1)掌握分支限界法的处理思路与算法框架。

 (2)掌握应用分支限界法解决具体问题的方法。

 (3)掌握分支限界法的广泛应用。

2.实验内容

(1)问题描述

image.png


 要求使用分支限界法解决该问题。

(2)输入

 输入包含3行。

image.png


(3)输出

image.png


3.问题实例分析

image.png


 堆(优先队列)是大根堆,“优先级”即判断函数为价值上界。

 此时大根堆堆顶为(“拿1,上界14.33”)。对其进行扩展,以是否拿2作为区分的依据。拿2时,价值上界为14.33。不拿2时,价值上界为14。将这两个结点都加入堆(优先队列)。

 此时大根堆堆顶为“拿2,上界14.33”。对其进行扩展,以是否拿3作为区分依据。拿3时,价值上界为14.33。不拿3时,价值上界为14。将这两个结点都加入堆(优先队列)。

 此时大根堆堆顶为“拿3,上界14.33”。对其进行扩展,以是否拿4作为区分依据。拿4时,背包此时体积超过上限,不可行。不拿4时,价值上界为14.25。将可行的右结点加入堆(优先队列)。

 此时大根堆堆顶为“不拿4,上界14.25”。对其进行扩展,以是否拿5作为区分依据。拿5时,背包此时体积超过上限,不可行。不拿5时,价值上界为13。将可行的右结点加入堆(优先队列)。

 此时大根堆堆顶为“不拿3,上界14”。对其进行扩展,以是否拿4作为区分依据。拿4时,价值上界为14。不拿4时,价值上界为10。这两个结点都可行,都加入堆(优先队列)。

 此时大根堆堆顶为“拿4,上界14”。对其进行扩展,以是否拿5作为区分依据。拿5时,价值上界为14。不拿5时,价值上界为9。这两个结点都可行,都加入堆(优先队列)。

image.png

4.算法描述及说明

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

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

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

 3.计算根结点上界,并将根结点加入大根堆。

 4.取出堆顶元素。若堆顶结点为解空间树的叶结点,则算法直接结束,叶结点的物品选取信息和价值为所求的最大价值。

 5.若堆顶元素不是叶结点,则尝试扩展左结点。若左结点可行(选取该物品背包体积没有被超出),则对左结点计算上界后入堆。扩展右结点,不选取物品,对右结点计算上界后入堆。

5.算法正确性分析

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

 分支限界的正确性分析:开始时,根结点是解空间树唯一的活结点,也是当前的扩展结点。算法会不断扩展结点,直到子集树的一个叶结点成为扩展结点时为止。此时优先队列中所有活结点的价值上界不超过该叶结点的价值。因此,该叶结点对应的解为问题最优解。

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

 从而,该算法是正确的。

6.算法时间复杂性分析

image.png


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

image.png

8.心得体会

9.程序源代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
double cw;//当前重量
double cp;//当前价值
double bestp;//当前最优价值
int n;//物品数量
double c;//背包容量
const int N = 105;
struct Bag {
  double w, v;
  int id, x;
};
int bestx[N];
Bag bag[N];
struct BBnode {
  BBnode *parent;
  bool leftChild;
  BBnode(BBnode* par, bool ch) {
    parent = par;
    leftChild = ch;
  }
};
struct heapnode {
  BBnode* livenode;
  double upperprofit;//价值上界
  double profit;//结点价值
  double weight;//结点重量
  int level;//层序号
  bool operator<(const heapnode& b) const {
    return this->upperprofit < b.upperprofit;
  }
  heapnode(BBnode *node,double up, double pp, double ww, int lev) {
    livenode = node;
    upperprofit = up;
    profit = pp;
    weight = ww;
    level = lev;
  }
};
bool cmp(Bag a, Bag b) {
  return (a.v / a.w) > (b.v / b.w);
}
bool cmpbound(heapnode a, heapnode b) {
  return a.upperprofit < b.upperprofit;
}
priority_queue<heapnode, vector<heapnode>,less<heapnode> > q;
void addlivenode(double up, double pp, double ww, int lev, BBnode* par, bool ch) {
  BBnode* b = new BBnode(par, ch);
  heapnode node(b, up, pp, ww, lev);
  q.push(node);
}
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 bfs() {
  BBnode *enode = NULL;
  int i = 1;
  bestp = 0;
  double up = bound(1);
  while (i != n + 1) {
    double wt = cw + bag[i].w;
    if (wt <= c) {
      if (cp + bag[i].v > bestp)
        bestp = cp + bag[i].v;
      addlivenode(up, cp + bag[i].v, cw + bag[i].w, i + 1, enode, true);
    }
    up = bound(i + 1);
    if (up > bestp)
      addlivenode(up, cp, cw, i + 1, enode, false);
    heapnode node = q.top();
    q.pop();
    enode = node.livenode;
    cw = node.weight;
    cp = node.profit;
    up = node.upperprofit;
    i = node.level;
  }
  for (int j = n; j > 0; j--) {
    bag[j].x = (enode->leftChild!=NULL) ? 1 : 0;
    enode = enode->parent;
  }
  for (int i = 1; i <= n; i++)
    bestx[bag[i].id] = bag[i].x;
  return;
}
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);
  bfs();
  cout << bestp << endl;
  for (int i = 1; i <= n; i++)
    cout << bestx[i] << " ";
  return 0;
}


目录
相关文章
|
14天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
47 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
17天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
18 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
10天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
26 4
|
17天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
13 0
数据结构与算法学习十四:常用排序算法总结和对比
|
9天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
19 0
|
15天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
22 0
|
17天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
17天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
14 0
|
5天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。