回溯算法

回溯算法

0-1背包: 即每种物品只有2 种选择，分别为：装入背包或不装入背包，物品数和背包容量已给定，计算装入背包物品的最大价值和最优装入方案，用回溯法搜索子集树的算法进行求解。对此模型我们刚好建立二叉树( 此处为完全二叉树)。对应的叶子节点数为: n! (n为顶点数)。

解子集树:

约束函数: cw+w[i]*x[i]<=c。(cw:当前背包重量;  w[i]*x[i]选中背包重量;  c:背包容量)

深度探索截止条件:i>n。(i:当前节点;  n:节点总数)

子集树结构:

思想: 对于每个物品若符合约束函数将当前节点加入到活动节点中 ，继续深度探索。若不符合直接将当前节点以及子树"剪枝"处理。当深度探索到叶子节点时。记录下此时背包最优值和对应的物品选择情况。然后从当前叶子节点往上回溯，重复刚才的回溯方法 。注意:  回溯要回溯到根。再由根探索树的另一边子树。当所有节点路径回溯完即可解决问题。

回溯方法代码:

void backpack(int i){if(i>n){if(cp>bestp){bestp = cp;for(int i =  1;i<=n;i++){     //到达叶子节点处物体的选择情况order[i] = x[i];}}}else{for(int j = 0;j<=1;j++){    //枚举物体i所有可能的路径，x[i] = j;if(cw+w[i]*x[i]<=c){   //满足约束,继续向子节点探索cp+=p[i]*x[i];cw+=w[i]*x[i];backpack(i+1);cp-=p[i]*x[i];   //回到上一层物体的选择情况cw-=w[i]*x[i];}}}
}

/**@回溯-0-1背包
*/
#include<iostream>
#include<algorithm>
#define MAX 100
using namespace std;
int   n;                     //背包数量
int   c;                    //背包容量
int   w[MAX];              //背包内物体重量
int   p[MAX];             //背包内物体价值
int   cp = 0;            //当前背包价值
int   cw = 0;           //当前背包重量
int   bestp = 0;       //最优背包价值
int   x[MAX];         //背包内物品进行选择
int   order[MAX];    //物品最终选中情况
void backpack(int i){if(i>n){if(cp>bestp){bestp = cp;for(int i =  1;i<=n;i++){     //到达叶子节点处物体的选择情况order[i] = x[i];}}}else{for(int j = 0;j<=1;j++){    //枚举物体i所有可能的路径，x[i] = j;if(cw+w[i]*x[i]<=c){   //约束为当前选择物品的重量不能超过背包剩余重量cp+=p[i]*x[i];cw+=w[i]*x[i];backpack(i+1);cp-=p[i]*x[i];   //回到上一层物体的选择情况cw-=w[i]*x[i];}}}
}
int main(){cout<<"请输入物品个数和背包最大容量:";cin>>n>>c;cout<<"输入各物品的重量和价值"<<endl;for(int i = 1;i<=n;i++){cin>>w[i]>>p[i];}backpack(1);  //    第一件物品默认为选中cout<<"最优价值为:"<<bestp<<endl;cout<<"物品的选中情况(选中为1,没有为0)"<<endl;for(int i = 1;i<=n;i++){cout<<order[i]<<" 选中的编号为:"<<i<<endl;}return 0;
}
/*
4 7
3 9
5 10
2 7
1 4
*/

0-1背包的动态规划解法:

类"排列树"法解0-1背包: .html