回溯法-0/1背包问题

2024-09-01 22:12
文章标签 问题 背包 回溯

本文主要是介绍回溯法-0/1背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是回溯法?

回溯法是一种搜索算法,它通过深度优先搜索的方式来解决决策问题。它从根节点开始,逐步扩展节点,直到找到所有可能的解。

回溯法的基本思想

  1. 开始节点:从根节点出发,这个节点是解空间的起点。
  2. 扩展节点:在当前节点上,选择一个方向继续搜索,这个方向会形成一个新的节点。
  3. 活节点与死节点:如果新节点有更多选择,它就是活节点;如果所有选择都已尝试,它就是死节点。
  4. 回溯:如果当前路径不是解,回溯到上一个活节点,尝试其他选择。

优化方法

为了提高搜索效率,我们使用两种剪枝技术:

  1. 剪枝一:如果当前物品的加入使得总重量超过背包容量,停止搜索这个方向。
  2. 剪枝二:如果剩余物品即使全部加入,也不能超过当前已知的最优解,停止搜索这个方向。

什么是0/1背包问题?

想象一下,你有一个背包,容量有限。你面前有n种不同的物品,每种物品都有自己的重量和价值。你的目标是选择一些物品放入背包,使得背包里物品的总价值最大,但总重量不能超过背包的容量。

算法描述

给定物品数量n,物品i的重量是wi>0,其价值为vi>0,背包的容量为c。我们的目标是找到一种物品组合,使得总价值最大,且总重量不超过c。

步骤

  1. 初始化:设置一个数组或列表来记录选择的物品。
  2. 递归函数:定义一个递归函数,接收当前物品索引、当前重量和当前价值作为参数。
  3. 边界条件:如果当前重量超过背包容量或已处理完所有物品,回溯。
  4. 选择与不选择:对于每种物品,尝试选择它或不选择它,然后递归调用函数。
  5. 更新最优解:每次找到一个解时,比较并更新已知的最优解。

0/1背包问题算法设计

算法目标

我们的目标是找出一个解向量 ( xi ),其中 ( xi = 0 ) 表示不放入物品 ( i ),( xi = 1 ) 表示放入物品 ( i )。

递归函数 Backtrack

  1. 叶子节点:如果 ( i > n ),我们到达了一个新的物品装包方案,更新最优价值。
  2. 扩展节点:如果 ( i < n ),当前节点在排列树的第 (i-1) 层,递归搜索子树,剪去不满足约束的节点。

实例

输入

  • 物品价值 ( V = {12, 11, 9, 8} )
  • 物品重量 ( W = {8, 6, 4, 3} )
  • 背包容量 ( B = 13 )

可行解

  • 解1: ( x = <0, 1, 1, 1> ) 选入物品2, 3, 4,总价值28,总重量13
  • 解2: ( x = <1, 0, 1, 0> ) 选入物品1, 3,总价值21,总重量12

最优解

  • 最优解: ( x = <0, 1, 1, 1> )

定义

  • ( CW )(Current Weight): 当前重量
  • ( CP )(Current Price): 当前价值

执行步骤

  1. 计算单位价值:降序排列物品。
  2. 从根节点出发:根节点代表当前扩展节点。
  3. 搜索左子树:判断物品是否装入背包。
    • 可行,更新 ( CW ) 和 ( CP ),继续遍历。
    • 不可行,回溯,尝试右子树。
  4. 计算上界 ( bound(i) ):
    • 若 ( bound(i) < bestp ),剪枝。
    • 否则,继续搜索。
  5. 叶子节点:比较 ( CP ) 与 ( bestp ),更新 ( bestp )。
  6. 遍历所有节点:完成搜索。

举例说明

已知 ( p = {45, 25, 24} ), ( w = {16, 15, 15} ), 背包容量为30,求最优价值。

步骤1:计算单位价值并排序

首先,我们需要计算每个物品的单位价值,即每个物品的价值除以其重量。然后,我们将物品按照单位价值从高到低进行排序。在这个例子中,物品的原始顺序恰好是单位价值降序排列。

步骤2:开始遍历并判断是否装入背包

我们将按照排序后的物品顺序,逐个考虑每个物品是否装入背包。

遍历过程说明

  • B1, B2:代表同一种物品B的不同节点。
  • C1, C2, C3, C4:代表同一种物品C的不同节点。
  • 这样的表示方法有助于我们区分在遍历过程中的不同节点。

具体步骤

  1. 考虑物品B1:首先尝试将物品B1装入背包。如果B1的重量加上当前背包重量(CW)不超过背包总容量(本例中为30),则B1可以装入背包。此时,背包重量更新为CW = 16,背包价值更新为CP = 45。

  2. 遍历B1的左子树:继续考虑B1后面的物品,如果剩余容量不足以装入下一个物品,我们就剪去这条路径。

  3. 进入B1的右子树:如果B1可以装入,我们继续考虑其他物品。在右子树中,我们到达物品C2,并计算上界值bound(i)。如果bound(i)大于当前最优价值bestp,则继续向下遍历。

  4. 到达叶子节点:如果在遍历中到达叶子节点,我们比较当前价值(CP)与最优价值(bestp),如果CP更大,则更新最优价值。

  5. 回溯:如果发现某条路径不可能产生更好的解,我们回溯到上一个决策点,尝试其他可能性。

示例遍历

  • 装入物品B1,CW = 16, CP = 45。
  • 尝试装入物品C1,但因剩余容量不足而剪枝。
  • 继续考虑C2,计算bound(i)=45+(25/15)**14=45+1.66*14=68.3,大于当前最优价值45,继续遍历。
  • 到达C2的叶子节点,记录最优价值bestp = 45。
  • 回溯,尝试其他物品B2,更新bound(i)为49,继续遍历。
  • 装入物品C3,CW = 15, CP = 25,继续考虑下一个物品。
  • 装入物品D5,CW = 30, CP = 49,更新最优价值bestp = 49。
  • 继续回溯,考虑其他可能的组合直到所有节点遍历完毕。

结果

经过所有可能的遍历和回溯,我们发现最优的背包装载方案价值为49,对应的物品组合为CD。

遍历过程图示

在这里插入图片描述
bound = 45+14*(24/15)=67.4

代码

#include <iostream> // 引入标准输入输出流库
#include <stdio.h>  // 引入C标准库,提供输入输出函数
using namespace std; // 使用标准命名空间// 定义全局变量
int n; // 物品数量
double c; // 背包容量
double v[100]; // 各个物品的价值数组
double w[100]; // 各个物品的重量数组
double cw = 0.0; // 当前背包重量
double cp = 0.0; // 当前背包中物品的总价值
double bestp = 0.0; // 记录找到的最优价值
double perp[100]; // 存储物品的单位价值,用于排序
int order[100]; // 存储物品的原始索引,用于排序后恢复
int put[100]; // 标记每个物品是否被选中放入背包,1表示放入,0表示不放入// 按单位价值对物品进行排序的函数
void knapsack() {int i, j; // 循环变量int temporder = 0; // 用于交换的临时变量double temp = 0.0; // 用于交换的临时变量// 计算每个物品的单位价值并存放到数组perp中for(i = 1; i <= n; i++) {perp[i] = v[i] / w[i];}// 使用冒泡排序算法按单位价值对物品进行排序for(i = 1; i <= n - 1; i++) {for(j = i + 1; j <= n; j++) {// 如果当前物品的单位价值小于下一个物品,则交换它们的位置if(perp[i] < perp[j]) {// 交换perp数组中的元素temp = perp[i];perp[i] = perp[j];perp[j] = temp;// 交换order数组中的元素,以保持物品原来的顺序temporder = order[i];order[i] = order[j];order[j] = temporder;// 交换v数组中的元素,以保持物品价值的一致性temp = v[i];v[i] = v[j];v[j] = temp;// 交换w数组中的元素,以保持物品重量的一致性temp = w[i];w[i] = w[j];w[j] = temp;}}}
}// 回溯函数,用于搜索最优解
void backtrack(int i) {// i表示当前正在考虑的物品索引if(i > n) { // 如果已经考虑完所有物品,则结束递归bestp = cp; // 更新最优价值为当前价值return;}// 如果当前物品可以放入背包,更新背包状态并继续搜索左子树if(cw + w[i] <= c) {cw += w[i]; // 将物品重量加到当前背包重量cp += v[i]; // 将物品价值加到当前背包价值put[i] = 1; // 标记当前物品已放入背包backtrack(i + 1); // 递归搜索下一件物品// 回溯,撤销上一步操作cw -= w[i];cp -= v[i];put[i] = 0;}// 计算当前扩展节点的上界,如果上界大于当前最优价值,则继续搜索右子树double boundValue = bound(i + 1);if(boundValue > bestp) {backtrack(i + 1);}
}// 计算上界函数,用于剪枝以减少搜索空间
double bound(int i) {// 计算剩余背包容量double leftw = c - cw;double b = cp; // 当前背包的总价值// 遍历剩余物品,尝试以单位价值递减的顺序装入背包while(i <= n && w[i] <= leftw) {leftw -= w[i]; // 更新剩余容量b += v[i]; // 更新总价值i++; // 移动到下一个物品}// 如果还有剩余容量,尝试用最大单位价值的物品填充if(i <= n) {b += (v[i] / w[i]) * leftw;}return b; // 返回计算出的上界
}// 主函数,程序入口点
int main() {int i; // 循环变量// 从用户那里获取物品数量和背包容量printf("请输入物品的数量和背包的容量:");scanf("%d %lf", &n, &c);// 从用户那里获取每个物品的重量printf("请依次输入%d个物品的重量:\n", n);for(i = 1; i <= n; i++) {scanf("%lf", &w[i]);order[i] = i; // 初始化物品的原始索引}// 从用户那里获取每个物品的价值printf("请依次输入%d个物品的价值:\n", n);for(i = 1; i <= n; i++) {scanf("%lf", &v[i]);}// 调用排序函数和回溯函数knapsack();backtrack(1);// 输出最优价值和需要装入背包的物品编号printf("最优价值为:%lf\n", bestp);printf("需要装入的物品编号是:");for(i = 1; i <= n; i++) {if(put[i] == 1) {printf("%d ", order[i]);}}printf("\n"); // 输出换行符,美化输出格式return 0; // 程序正常结束
}

在这里插入图片描述

时间复杂度

因为物品只有选与不选2个决策,而总共有n个物品,所以时间复杂度为在这里插入图片描述

因为递归栈最多达到n层,而且存储所有物品的信息也只需要常数个一维数组,所以最终的空间复杂度为O(n)。

这篇关于回溯法-0/1背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1128190

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符