算法分析与设计--0/1背包问题(回溯法)
问题描述:
给定n种物品和一个容量为C的背包,物品i的重量是wi,其价值为vi,0/1背包问题是如何选择装入背包的物品(物品不可分割),使得装入背包中物品的总价值最大?
#include<iostream>
using namespace std;
const int n = 3; //物品个数
const int C = 25; //背包容量
int bestP = 0; //最大价值
int w[n] = {20,15, 10}; //物品重量
int p[n] = {20,30, 25}; //物品价值
int cp = 0; //当前背包价值
int cw = 0; //当前背包重量
//w[n]存储物品的重量,p[n]存储价值
//这个方法用来排序,单位价值由大到小
void sortValue(int w[], int p[],int n)
{
int index;
int temp; //暂存变量
for(int i = 0; i < n - 1; i++)
{
index = i;
for(int j = i + 1; j < n; j++)
{
//单位重量价值的比较
if((p[j] / w[j]) > (p[index] / w[index]))
{
index = j;
}
}
if(index != i) //交换记录,同时更新w和p数组
{
//交换价值记录
temp = p[index];
p[index] = p[i];
p[i] = temp;
//交换重量记录
temp = w[index];
w[index] = w[i];
w[i] = temp;
}
}
}
int Bound(int i)
{
//计算节点所相应价值的上界
int cleft = C - cw; //剩余容量
int b = cp;
//以物品单位重量价值递减顺序装入物品
while(i < n && w[i] <= cleft)
{
cleft -= w[i];
b += p[i];
i++;
}
if(i <= n)
{
b += p[i] * cleft / w[i];
}
return b;
}
//回溯求解0/1背包,寻找可行解
void BackTrack(int i)
{
if(i > n - 1)
{
bestP = cp;
return;
}
if(cw + w[i] <= C) //当前结点加上下一个结点的重量小于或等于总的背包容量
{ //进入左子树,也就是说w[i]被装入背包
cw = cw + w[i]; //背包当前的重量
cp = cp + p[i]; //当前获得的价值
BackTrack(i + 1);
//回溯,进入右子树
cw = cw - w[i];
cp = cp - p[i];
}
if(Bound(i+1) > bestP)
{
BackTrack(i + 1);
}
}
void putPackage(int w[],int p[])
{
BackTrack(0); //从根结点开始
cout<<"背包的最大价值:"<<bestP<<endl;
}
int main()
{
for(int i = 0; i < n; i++)
{
cout<<w[i]<<" ";
}
cout<<endl;
for(int i = 0; i < n; i++)
{
cout<<p[i]<<" ";
}
cout<<endl;
putPackage(w,p);
system("pause");
return 0;
}
分享到:
相关推荐
利用回溯算法解决0/1背包问题。类knapsack为背包类,bound是上界函数,函数bknapsack实现0/1背包回溯算法。内有详细注释。
算法设计实验报告,包括:蛮力、动态规划、回溯、分支限界四种算法求解0/1背包问题的基本思想、时间复杂度分析,C++实现代码,运行结果截图,实验心得。
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
回溯法 0-1背包问题 计算机算法设计与分析 回溯法 背包问题
3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现与算法的效率分析。 4) 分支限界法求解问题的一般思路,分支限界法求解本问题的思路及其C/C++程序实现与算法的效率分析。 有代码!!
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
利用回溯法解0-1背包问题讲解,程序调试VC++6.0通过
算法分析与设计 回溯法 背包问题 递归与迭代
使用回溯法实现的01背包问题,代码十分的简短,易懂,但是效率低,未优化。
算法分析与设计实验报告书:回溯算法之背包问题。 实验目的和要求 (1)掌握回溯法的设计思想; (2)掌握解空间树的构造方法,以及在求解过程中如何存储求解路径; (3)考察回溯法求解问题的有效程度。 (4)设计...
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
本例采用java实现的0-1背包问题,采用的是回溯法,参考算法设计与分析(第二版)
全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.学习并掌握回溯法 2.利用迭代回溯和递归回溯两种方法解决01背包问题。 预览地址:
实验二 用动态规划法求解0/1背包问题 实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0...
C语言实现01背包问题 回溯法 算法分析题答案
用回溯法解0_1背包问题时,会用到状态空间树。在搜索状态空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索,否则将右子树剪去。设r是当前剩余物品价值...
"0-1"背包问题的贪心算法 "0-1"背包问题的动态规划算法 "0-1"背包问题的回溯算法
0-1背包_回溯算法,VC++全程编写,结构体,易学易用
用回溯法实现0-1 背包问题,适合刚刚学习算法分析的朋友。
回溯法、分支限界法解0-1背包问题(就设计算法设计与分析实验报告).doc