龙文区城乡建设局网站,wordpress成功案例,网站引导视频怎么做,自己做网站主机目录
回溯算法--01背包问题
[算法描述]
[回溯法基本思想]
法一#xff1a;
法二#xff1a;
代码#xff1a; 运行结果
代码改进 回溯算法--01背包问题
[算法描述]
0-1背包问题是子集选取问题。一般情况下#xff0c;0-1背包问题是NP完全问题。0-1背包问题的解空…
目录
回溯算法--01背包问题
[算法描述]
[回溯法基本思想]
法一
法二
代码 运行结果
代码改进 回溯算法--01背包问题
[算法描述]
0-1背包问题是子集选取问题。一般情况下0-1背包问题是NP完全问题。0-1背包问题的解空间可以用子集树表示。解0-1背包问题的回溯法与解装载问题的回溯法十分相似。在搜索解空间树时只要其左儿子节点是一个可行的节点搜索就进入其左子树;而当右子树中有可能包含最优解时才进入右子树搜索否则将右子树剪去。设r是当前剩余物品价值总和cp是当前价值bestp是当前最优价值。当cprbestp时可剪去右子树。计算右子树中解的上界的更好的办法是将剩余物品依其单位重量价值排序然后依次装入物品直至装不下时再装入该物品的一部分而装满背包由此得到的价值是右子树的上界。
0--1背包的一个实例
n3, c50,
w{103020},
v(p){60120100}的
0-1背包问题的最优解和最优值。w为重量v为价值量n为物品个数c为背包容量
[回溯法基本思想]
确定了解空间的组织结构后【回溯法从开始节点根节点出发以深度优先搜索整个解空间。这个开始的节点为活节点同时成为当前的扩展节点。在当前的扩展节点处搜素向纵深方向移至一个新节点。这个新节点就成为新的活节点并成为当前扩展节点。如果当前节点处不能再向纵深方向移动则当前扩展节点为死节点。此时应往回移动到最近的一个活节点处。回溯法以这种方式递归的在解空间中搜素直至找到所有符合要求的解或解空间中已无活节点。】即深度优先搜索
【优化方法】
剪枝一当前决策放入的物品总重量已经大于背包容量时没有必要继续决策此时可以将其左子树剪掉。
剪枝二如果将当前扩展节点后剩下的所有物品都装入还没有目前已求得的最优值大的话就不在进行决策了直接返回。
递归回溯时在当前扩展节点处会通过设置约束函数和限界函数。不满足条件的剪去相应的子树
【0-1背包算法分析】
对于0-1背包问题可用一颗完全二叉树表示其解空间针对上述实例n5解空间树有32个可能的解解空间树如下图所示。 法一 回溯算法是一种解决问题的通用算法能够在一个问题的所有解空间中按深度优先的策略搜索直到找到所需要的解或者搜索完整个解空间都没有找到解。0-1背包问题是指在限制背包容量的情况下在一堆物品中选择一部分使得这些物品的总价值最大。 C 设计回溯算法解决 0-1 背包问题的思路如下 定义一个全局数组 max_value用于存储当前找到的最大总价值定义一个局部数组 current_weight用于存储当前已选物品的总重量定义一个递归函数 backpack用于搜索某一层的所有可能性在 backpack 函数中首先判断是否已经遍历完所有物品如果是则更新数组 max_value如果还没有处理完所有物品则需要对当前物品进行判断。如果当前物品的重量加上当前已选物品的总重量仍然小于等于背包容量则将当前物品加入已选物品中并进入下一层搜索。否则不加入当前物品并进入下一层搜索。在递归返回后需要将当前物品从已选物品中删除以方便下一次搜索。一个简单的 C 回溯算法解决 0-1 背包问题的示例代码如下
/*
* 回溯算法---0-1背包问题
*/
#include iostream
using namespace std;const int max_n 10;
const int capacity 50;int w[] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 }; // 物品重量数组
int v[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // 物品价值数组
bool selected[max_n]; // 记录物品是否被选择
int current_weight 0; // 当前已选物品的总重量
int max_value 0; // 已找到的最大总价值// backpack 函数用于搜索某一层的所有可能性
void backpack(int i) {if (i max_n) { // 如果已经遍历完所有物品则更新 max_valueif (current_weight capacity max_value v[i]) {max_value v[i];}return;}if (current_weight w[i] capacity) { // 如果能将当前物品加入背包selected[i] true;current_weight w[i];backpack(i 1); // 进入下一层current_weight - w[i]; // 递归返回后需要将当前物品从已选物品中删除selected[i] false;}backpack(i 1); // 进入下一层
}int main() {backpack(0); // 从第一个物品开始搜索cout 最大总价值为 max_value endl;return 0;
}法二
代码
头文件
#pragma once
#includeiostream
#includecmath
#includevector
#include algorithm
using namespace std;
源文件
/*
* 回溯算法--01背包
*/
#include01背包头文件.hconst int NUM 50;
int c; //背包容纳的重量
int n; //物品数量
int cw; //当前重量
int cv; //当前价值
int bestv; //当前最优价值//描述每个物品的数据结构
struct Object {int w; //物品的重量int v; //物品的价值double d; //物品的单位价值重量比dv/w
}Q[NUM]; //物品的数组bool cmp(Object a,Object b) {if (a.db.d){return true;}else{return false;}
}
//限界函数Bound()的实现
//形参i是回溯的深度
int Bound(int i) {int cleft c - cw; // 背包剩余容纳的重量double b cv; // 上界价值while (i n Q[i].w cleft) { // 尽量装满背包cleft - Q[i].w;b Q[i].v;i;}if (i n) { // 剩余空间不足以容纳物品 i 时将物品 i 分配到背包中直到背包装满b 1.0 * Q[i].v / Q[i].w * cleft;}return b;
}//形参i是回溯的深度从0开始
void backtrack(int i){if (i 1 n) {bestv cv;return;}//进入左子树搜索if(cwQ[i].wc) {cw cw Q[i].w;cv cv Q[i].v;backtrack(i 1);cw cw - Q[i].w;cv cv - Q[i].v;}//进入右子树搜索if(Bound(i1)bestv){backtrack(i 1);}
}int main() {cin c n; //输入背包容纳的重量和物品数量for (int i 0; i n; i) {cin Q[i].w Q[i].v; //输入物品的重量和物品的价值Q[i].d 1.0 * Q[i].v / Q[i].w; //物品的单位价值重量比dv/w} //排序sort(Q, Q n, cmp);backtrack(0);cout 最大总价值为 bestv endl; return 0;
} 运行结果 代码改进
上面的代码已经实现了 01 背包问题的求解但是还有一些需要改进的地方以下是我的建议 你在回溯函数 backtrack 中使用递归的方式进行搜索。虽然递归可以使得代码更加简洁但是如果物品数量较大时可能会导致栈溢出的问题。因此建议采用迭代的方式进行搜索使用一个栈来存储搜索状态。 在你的排序函数中其实不必写成一个 bool 类型的函数直接写成一个比较函数即可。例如
bool cmp(Object a, Object b) {return a.d b.d;
}3.你在计算排序后的上界时可能会出现除数为 0 的情况当背包容量为 0 时。因此在计算物品的单位价值时可以加上一个特判例如
if (Q[i].w 0) {Q[i].d 0;
} else {Q[i].d 1.0 * Q[i].v / Q[i].w;
}4.下面是修改过的代码
/** 01 背包问题求解回溯法实现* 输入格式* 第一行包含背包容量 c 和物品数量 n以空格分隔* 接下来 n 行每行包含一个物品的重量和价值以空格分隔。* 输出格式* 最大总价值*/#include iostream
#include vector
#include algorithm
using namespace std;const int MAXN 50;struct Object {int w, v; // 物品重量和价值double d; // 单位价值
};bool cmp(Object a, Object b) {return a.d b.d;
}int main() {int c, n;cin c n;vectorObject items(n);for (int i 0; i n; i) {cin items[i].w items[i].v;if (items[i].w 0) {items[i].d 0;} else {items[i].d 1.0 * items[i].v / items[i].w;}}sort(items.begin(), items.end(), cmp); // 按单位价值排序int bestv 0; // 当前最优解vectorint path(n); // 存储当前搜索路径int i 0; // 当前搜索的物品编号int cw 0; // 当前背包中物品的总重量int cv 0; // 当前背包中物品的总价值while (true) {if (i n) { // 遍历完了所有物品回溯if (bestv cv) {bestv cv;}if (path.empty()) {break; // 遍历完了所有状态退出}i path.back(); // 取出上一个搜索的物品path.pop_back();cw - items[i].w;cv - items[i].v;i; // 进入右子树搜索} else if (cw items[i].w c) { // 左子树搜索path.push_back(i);cw items[i].w;cv items[i].v;i; // 进入左子树搜索} else { // 右子树搜索double bound cv (c - cw) * items[i].d; // 计算上界if (bound bestv) {if (path.empty()) {break; // 遍历完了所有状态退出}i path.back(); // 取出上一个搜索的物品path.pop_back();cw - items[i].w;cv - items[i].v;i; // 进入右子树搜索} else {i; // 进入左子树搜索}}}cout bestv endl;return 0;
}这段代码实现了 01 背包问题的回溯算法求解并且采用了剪枝策略进行优化基本思路如下 首先读入背包容量 c 和物品数量 n以及每个物品的重量和价值。 将物品按单位价值从大到小排序这里采用了 C STL 中的 sort 函数。 从第一个物品开始进行搜索使用一个栈来保存搜索路径路径上的每个节点包含当前已选中的物品编号、当前背包中已装载的物品总重量和总价值。 在搜索过程中对于每个节点分别考虑进入其左子树和右子树两种情况。左子树表示当前物品被选择放入背包进入左子树后要将物品的重量和价值加入到当前背包中并更新搜索路径右子树表示当前物品不放入背包进入右子树后只需要更新搜索路径即可。 在进入下一个节点之前使用剪枝策略计算这个节点的上界。这里使用了线性松弛法Linear Relaxation即假设当前物品可以部分装入背包中按单位价值从大到小的顺序装入物品直到背包装满则此时背包中物品的总价值加上剩余空间能够容纳的物品的单位价值乘以其重量即为当前节点的上界。如果计算出来的上界小于当前已知的最优解则可以剪枝放弃进入左子树的搜索直接进入右子树。因为进入左子树的搜索必然不会得到更优的解。 当遍历完所有节点后输出当前的最优解即可。 总体而言这段代码实现了一个简洁高效的 01 背包问题求解算法。
