【回溯法】－－01背包问题
1、问题描述
给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ （要求使用回溯法）
例如：
２、算法分析
【整体思路】
01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。
在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。
上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。
为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。
【举例说明】
对于n=4的0/1背包问题，其解空间树如图所示，树中的16个叶子结点分别代表该问题的16个可能解。
【算法设计】
利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi （即对n个物品放或不放的一种的方案）
其中， (ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包）。
在递归函数Backtrack中，
当i>n时，算法搜索至叶子结点，得到一个新的物品装包方案。此时算法适时更新当前的最优价值
当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
【时间复杂度&&优化】
因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为
。
因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。
【源代码】
-
#include <iostream>
-
#include <stdio.h>
-
//#include <conio.h>
-
using
namespace
std;
-
int n;
//物品数量
-
double c;
//背包容量
-
double v[
100];
//各个物品的价值 value
-
double w[
100];
//各个物品的重量 weight
-
double cw =
0.0;
//当前背包重量 current weight
-
double cp =
0.0;
//当前背包中物品总价值 current value
-
double bestp =
0.0;
//当前最优价值best price
-
double perp[
100];
//单位物品价值(排序后) per price
-
int order[
100];
//物品编号
-
int put[
100];
//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据
-
-
-
//按单位价值排序
-
void knapsack()
-
{
-
int i,j;
-
int temporder =
0;
-
double temp =
0.0;
-
-
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[],order[],sortv[],sortw[]
-
{
-
temp = perp[i];
//冒泡对perp[]排序
-
perp[i]=perp[j];
-
perp[j]=temp;
-
-
temporder=order[i];
//冒泡对order[]排序
-
order[i]=order[j];
-
order[j]=temporder;
-
-
temp = v[i];
//冒泡对v[]排序
-
v[i]=v[j];
-
v[j]=temp;
-
-
temp=w[i];
//冒泡对w[]排序
-
w[i]=w[j];
-
w[j]=temp;
-
}
-
}
-
}
-
-
//回溯函数
-
void backtrack(int i)
-
{
//i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品
-
double bound(int i);
-
if(i>n)
//递归结束的判定条件
-
{
-
bestp = cp;
-
return;
-
}
-
//如若左子节点可行，则直接搜索左子树;
-
//对于右子树，先计算上界函数，以判断是否将其减去
-
if(cw+w[i]<=c)
//将物品i放入背包,搜索左子树
-
{
-
cw+=w[i];
//同步更新当前背包的重量
-
cp+=v[i];
//同步更新当前背包的总价值
-
put[i]=
1;
-
backtrack(i+
1);
//深度搜索进入下一层
-
cw-=w[i];
//回溯复原
-
cp-=v[i];
//回溯复原
-
}
-
if(bound(i+
1)>bestp)
//如若符合条件则搜索右子树
-
backtrack(i+
1);
-
}
-
-
//计算上界函数，功能为剪枝
-
double bound(int i)
-
{
//判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值
-
double leftw= c-cw;
//剩余背包容量
-
double b = cp;
//记录当前背包的总价值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("请输入物品的重量和价值：\n");
-
for(i=1;i<=n;i++)
-
{
-
printf("第%d个物品的重量：",i);
-
scanf("%lf",&w[i]);
-
printf("第%d个物品的价值是：",i);
-
scanf("%lf",&v[i]);
-
order[i]=i;
-
}*/
-
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]);
-
}
-
return
0;
-
}
转载：https://blog.csdn.net/qian2213762498/article/details/79420269