回溯算法--01背包问题

这篇具有很好参考价值的文章主要介绍了回溯算法--01背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

回溯算法--01背包问题

[算法描述]

[回溯法基本思想]

法一:

法二: 

代码:

 运行结果

代码改进 


回溯算法--01背包问题

[算法描述]

0-1背包问题是子集选取问题。一般情况下,0-1背包问题是NP完全问题。0-1背包问题的解空间可以用子集树表示。解0-1背包问题的回溯法与解装载问题的回溯法十分相似。在搜索解空间树时,只要其左儿子节点是一个可行的节点,搜索就进入其左子树;而当右子树中有可能包含最优解时才进入右子树搜索,否则将右子树剪去。设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+r<=bestp时,可剪去右子树。计算右子树中解的上界的更好的办法是,将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包,由此得到的价值是右子树的上界。

0--1背包的一个实例:

n=3, c=50,

w={10,30,20},

v(p)={60,120,100}的

0-1背包问题的最优解和最优值。<w为重量,v为价值量,n为物品个数,c为背包容量>
 

[回溯法基本思想]

确定了解空间的组织结构后,【回溯法从开始节点(根节点)出发,以深度优先搜索整个解空间。这个开始的节点为活节点,同时成为当前的扩展节点。在当前的扩展节点处,搜素向纵深方向移至一个新节点。这个新节点就成为新的活节点,并成为当前扩展节点。如果当前节点处不能再向纵深方向移动,则当前扩展节点为死节点。此时,应往回移动到最近的一个活节点处。回溯法以这种方式递归的在解空间中搜素,直至找到所有符合要求的解或解空间中已无活节点。】(即深度优先搜索)

【优化方法】

剪枝(一):当前决策放入的物品总重量已经大于背包容量时,没有必要继续决策,此时可以将其左子树剪掉。

剪枝(二):如果将当前扩展节点后剩下的所有物品都装入还没有目前已求得的最优值大的话,就不在进行决策了,直接返回。

递归回溯时,在当前扩展节点处会通过设置约束函数和限界函数。不满足条件的,剪去相应的子树

【0-1背包算法分析】

对于0-1背包问题,可用一颗完全二叉树表示其解空间,针对上述实例(n=5),解空间树有32个可能的解,解空间树如下图所示。

回溯算法--01背包问题

法一:

回溯算法是一种解决问题的通用算法,能够在一个问题的所有解空间中,按深度优先的策略搜索,直到找到所需要的解或者搜索完整个解空间都没有找到解。0-1背包问题是指在限制背包容量的情况下,在一堆物品中选择一部分,使得这些物品的总价值最大。

C++ 设计回溯算法解决 0-1 背包问题的思路如下:

  1. 定义一个全局数组 max_value,用于存储当前找到的最大总价值;
  2. 定义一个局部数组 current_weight,用于存储当前已选物品的总重量;
  3. 定义一个递归函数 backpack,用于搜索某一层的所有可能性;
  4. 在 backpack 函数中,首先判断是否已经遍历完所有物品,如果是则更新数组 max_value;
  5. 如果还没有处理完所有物品,则需要对当前物品进行判断。如果当前物品的重量加上当前已选物品的总重量仍然小于等于背包容量,则将当前物品加入已选物品中,并进入下一层搜索。否则,不加入当前物品,并进入下一层搜索。
  6. 在递归返回后,需要将当前物品从已选物品中删除,以方便下一次搜索。

一个简单的 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_value
        if (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
#include<iostream>
#include<cmath>
#include<vector>
#include < algorithm>
using namespace std;

源文件:

/*
* 回溯算法--01背包
*/
#include"01背包头文件.h"

const int NUM = 50;
int c;		//背包容纳的重量
int n;		//物品数量
int cw;		//当前重量
int cv;		//当前价值
int bestv;	//当前最优价值

//描述每个物品的数据结构
struct Object {
	int w;		//物品的重量
	int v;		//物品的价值
	double d;	//物品的单位价值重量比(d=v/w)
}Q[NUM];		//物品的数组

bool cmp(Object a,Object b) {
	if (a.d>b.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(cw+Q[i].w<=c) {
		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(i+1)>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;		//物品的单位价值重量比(d=v/w)
	}				

	//排序
	sort(Q, Q + n, cmp);
	backtrack(0);
	cout << "最大总价值为:" << bestv << endl;   
	return 0;			
}

 运行结果

回溯算法--01背包问题

代码改进 

上面的代码已经实现了 01 背包问题的求解,但是还有一些需要改进的地方,以下是我的建议:

  1. 你在回溯函数 backtrack 中使用递归的方式进行搜索。虽然递归可以使得代码更加简洁,但是如果物品数量较大时,可能会导致栈溢出的问题。因此,建议采用迭代的方式进行搜索,使用一个栈来存储搜索状态。

  2. 在你的排序函数中,其实不必写成一个 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;
    vector<Object> 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;  // 当前最优解
    vector<int> 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 背包问题的回溯算法求解,并且采用了剪枝策略进行优化,基本思路如下:

  1. 首先,读入背包容量 c 和物品数量 n,以及每个物品的重量和价值。

  2. 将物品按单位价值从大到小排序,这里采用了 C++ STL 中的 sort 函数。

  3. 从第一个物品开始进行搜索,使用一个栈来保存搜索路径,路径上的每个节点包含当前已选中的物品编号、当前背包中已装载的物品总重量和总价值。

  4. 在搜索过程中,对于每个节点,分别考虑进入其左子树和右子树两种情况。左子树表示当前物品被选择放入背包,进入左子树后要将物品的重量和价值加入到当前背包中,并更新搜索路径;右子树表示当前物品不放入背包,进入右子树后只需要更新搜索路径即可。

  5. 在进入下一个节点之前,使用剪枝策略计算这个节点的上界。这里使用了线性松弛法(Linear Relaxation),即假设当前物品可以部分装入背包中,按单位价值从大到小的顺序装入物品直到背包装满,则此时背包中物品的总价值加上剩余空间能够容纳的物品的单位价值乘以其重量即为当前节点的上界。如果计算出来的上界小于当前已知的最优解,则可以剪枝,放弃进入左子树的搜索,直接进入右子树。因为进入左子树的搜索必然不会得到更优的解。

  6. 当遍历完所有节点后,输出当前的最优解即可。

总体而言,这段代码实现了一个简洁高效的 01 背包问题求解算法。

 文章来源地址https://www.toymoban.com/news/detail-405524.html

到了这里,关于回溯算法--01背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 湘潭大学 算法设计与分析实验 回溯 动态规划 贪心 模拟退火解决背包问题

    https://download.csdn.net/download/SQ_ZengYX/88620871 测试用例

    2024年02月02日
    浏览(62)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(56)
  • 算法设计 - 01背包问题

    学习来源 【自制】01背包问题算法动画讲解_哔哩哔哩_bilibili 问题描述 有N件物品,第i件物品的重量是w[i],价值是p[i]。 有一个背包,背包的承重是W。 求解:将哪些物品装入背包可获得最大价值。 实例说明 有如下物品,给定每件物品的重量和价值: 物品 重量 价值 葡萄 2

    2023年04月08日
    浏览(43)
  • 算法训练第四十二天|01背包问题 二维 、01背包问题 一维、416. 分割等和子集

    视频链接:https://www.bilibili.com/video/BV1cg411g7Y6/ 参考:https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。 而完全背包又是也是01背包稍作变化而来,即:完全

    2024年02月01日
    浏览(46)
  • 算法学习17-动态规划01:背包问题

    提示:以下是本篇文章正文内容: 提示:这里对文章进行总结: 💕💕💕

    2024年04月27日
    浏览(53)
  • 【算法5.1】背包问题 - 01背包 (至多最大价值、至少最小价值)

    目录 至少模板和至多模板的两大区别 1、至多模板 2、至少模板 2. 01背包 - 至多模板 - 体积至多j,总价值最大 1、朴素做法 - 二维dp  2、优化 - 一维dp 4700. 何以包邮? - 至少模板 - 价值至少j,总价值最小   初始化不同 : 至多模板求的是最大值,所以初始化为f[0~m]=0 至少模

    2024年02月12日
    浏览(39)
  • 算法套路十四——动态规划之背包问题:01背包、完全背包及各种变形

    如果对递归、记忆化搜索及动态规划的概念与关系不太理解,可以前往阅读算法套路十三——动态规划DP入门 背包DP介绍:https://oi-wiki.org/dp/knapsack/ 0-1背包:有n个物品,第i个物品的体积为w[i],价值为v[i],每个物品至多选一个, 求体积和不超过capacity时的最大价值和,其中i从

    2024年02月10日
    浏览(60)
  • 【动态规划】01背包问题——算法设计与分析

    若超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走,则如何选择可以使得收益最高? 商品 价格 体积 啤酒 24 10 汽水 2 3 饼干 9 4 面包 10 5 牛奶 9 4 0-1 Knapsack Problem 输入: quad - n n n 个商品组成集合 O O O ,每个商品有属性价格 p i p_i p i ​ 和体积 v i v_i v

    2024年02月04日
    浏览(79)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(56)
  • 【Java实现】动态规划算法解决01背包问题

    1、问题描述: 一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大? 2、动态规划算法的概述 1)动态规划(Dynamic Progra

    2023年04月09日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包