算法设计与分析文档(修改版)1
需积分: 0 8 浏览量
2022-08-08
21:59:40
上传
评论
收藏 53KB DOCX 举报
算法设计与分析——多维背包问题
问题描述：
多维背包给定 N 种物品，每种物品有 M 个属性，每种属性有对应的约束条件，要
求物品的所有属性在满足对应约束条件的情况的同时，获取到背包的最大价值。
简单来说，就是在经典的 0-1 背包问题上多增加了一个维度进行分析。
回溯法解决多维背包问题：
利用回溯法解决多维背包问题是一个子集选取问题，适合于用子集树表示多维背
包问题的解空间。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索
就进入左子树，在右子树中可能含有最优解时才进入右子树搜索。否则将右子树
剪去。回溯法解决多维背包问题的时间复杂度和空间复杂度均为 O(n)。
伪代码：
//回溯函数
Void BackTrack(int k)
{//已搜索到根节点
if(k>物品数量) //如果搜索到叶子节点
{
if(当前背包的 nowValue 大于上一次的 maxValue)
{
maxValue=nowValue;
}
}
//else 遍历左子树
if(当前所选物品的 nowShuxing[i]+shuxing[i][k]<=背包的约束值 yueshu[i])
{
nowShuxing[i]+=shuxing[i][k];
}
nowValue+=value[k];
BackTrack(k+1); //不选择物品则回溯恢复原来的约束情况
nowShuxing[i] -= shuxing[i][k];
nowValue -= value[k];
//找不到最优解，则开始遍历右子树
BackTrack(k+1);
//找到最优解，输出最大价值
资源评论
