回溯法-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。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小 对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了 状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的 代码如下： #include<iostream>#include<
阅读更多...
hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的 状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值 代码如下： #include<iostream>#include<algorithm>#include<
阅读更多...
csu(背包的变形题)

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2