限界与剪枝求解0/1背包问题
一、 算法思想描述
首先对物体按照价值重量比进行排序。
再从第一个物体开始，对每个物体分两种状态求解：放入与不放入。
在每次求解时都计算该状态可能达到的最优价值，并放入大顶堆中。
当两种状态都求解完后从堆中取出堆顶元素，从该元素所代表的状态中继续进行分支计算。直到深度达到n，问题得到解。
二、 完整的程序以及说明
-
#include<iostream>
-
#include<algorithm>
-
using namespace std;
-
-
// 最多可能物体数
-
#define N 10
-
-
// 物体结构体
-
typedef struct {
-
float w; // 重量
-
float p; // 价值
-
float v; // 价值重量比
-
int num; // 编号
-
} OBJECT;
-
-
// 状态结构体
-
typedef struct {
-
bool s1[N]; // 当前放入物体
-
int k; // 搜索深度
-
float b; // 价值上界
-
float w; // 物体重量
-
float p; // 物体价值
-
} KNAPNODE;
-
-
// 堆元素结构体
-
typedef struct {
-
KNAPNODE *p;// 结点数据
-
float b; // 所指结点的上界
-
} HEAP;
-
-
/* 比较两个物体的价值比 */
-
bool cmp(OBJECT a, OBJECT b){
-
return a.v>b.v;
-
}
-
-
/* 交换两个堆元素 */
-
void swap(HEAP &a, HEAP &b){
-
HEAP tmp = a;
-
a = b;
-
b = tmp;
-
}
-
-
/* 堆中元素上移 */
-
void sift_up(HEAP H[], int i){
-
bool done = false;
-
if(i!=1){
-
while(!done && i!=1){
-
if(H[i].b>H[i/2].b){
-
swap(H[i], H[i/2]);
-
}else{
-
done = true;
-
}
-
i = i/2;
-
}
-
}
-
}
-
-
/* 堆中元素下移 */
-
void sift_down(HEAP H[], int n, int i){
-
bool done = false;
-
if((2*i)<=n){
-
while(!done && ((i = 2*i) <= n)){
-
if(i+1<=n && H[i+1].b > H[i].b){
-
i++;
-
}
-
if(H[i/2].b<H[i].b){
-
swap(H[i/2], H[i]);
-
}else{
-
done = true;
-
}
-
}
-
}
-
}
-
-
/* 往堆中插入结点 */
-
void insert(HEAP H[], HEAP x, int &n){
-
n++;
-
H[n] = x;
-
sift_up(H,n);
-
}
-
-
/* 删除堆中结点 */
-
void del(HEAP H[], int &n, int i){
-
HEAP x, y;
-
x = H[i]; y = H[n];
-
n --;
-
if(i<=n){
-
H[i] = y;
-
if(y.b>=x.b){
-
sift_up(H,i);
-
}else{
-
sift_down(H, n, i);
-
}
-
}
-
}
-
-
/* 获得堆顶元素并删除 */
-
HEAP delete_max(HEAP H[], int &n){
-
HEAP x = H[1];
-
del(H, n, 1);
-
return x;
-
}
-
-
/* 计算分支节点的上界 */
-
void bound( KNAPNODE* node, float M, OBJECT ob[], int n){
-
int i = node->k;
-
float w = node->w;
-
float p = node->p;
-
if(node->w>M){ // 物体重量超过背包载重量
-
node->b = 0; // 上界置为0
-
}else{
-
while((w+ob[i].w<=M)&&(i<n)){ // 否则
-
w += ob[i].w; // 计算背包已装入载重
-
p += ob[i++].p; // 计算背包已装入价值
-
}
-
if(i<n){
-
node->b = p + (M - w)*ob[i].p/ob[i].w;
-
}else{
-
node -> b = p;
-
}
-
}
-
}
-
-
/*
-
* 用分支限界法实现0/1背包问题
-
* 输入：包含n个物体的重量和价值的数组ob[]，背包载重量M
-
* 输出：最优装入背包的物体obx[]，装入背包的物体最优价值v
-
*/
-
float knapsack_bound(OBJECT ob[], float M, int n, int obx[]){
-
int i, k = 0; // 堆中元素个数的计数器初始化为0
-
float v;
-
KNAPNODE *xnode, *ynode, *znode;
-
HEAP x, y, z, *heap;
-
heap = new HEAP[n*n]; // 分配堆的存储空间
-
for( i=0; i<n; i++){
-
ob[i].v = ob[i].p/ob[i].w; // 计算物体的价值重量比
-
ob[i].num = i; // 记录物体的初始序号
-
}
-
sort(ob,ob+n,cmp); // 对物体按照价值重量比排序
-
xnode = new KNAPNODE; // 建立父亲结点
-
for( i=0; i<n; i++){ // 初始化结点
-
xnode->s1[i] = false;
-
}
-
xnode->k = xnode->w = xnode->p = 0;
-
while(xnode->k<n) {
-
ynode = new KNAPNODE; // 建立结点y
-
*ynode = *xnode; // 结点x的数据复制到结点y
-
ynode->s1[ynode->k] = true; // 装入第k个物体
-
ynode->w += ob[ynode->k].w; // 背包中物体重量累计
-
ynode->p += ob[ynode->k].p; // 背包中物体价值累计
-
ynode->k ++; // 搜索深度++
-
bound(ynode, M, ob, n); // 计算结点y的上界
-
y.b = ynode->b;
-
y.p = ynode;
-
insert(heap, y, k); // 结点y按上界的值插入堆中
-
znode = new KNAPNODE; // 建立结点z
-
*znode = *xnode; // 结点x的数据复制到结点z
-
znode->k++; // 搜索深度++
-
bound(znode, M, ob, n); // 计算节点z的上界
-
z.b = znode->b;
-
z.p = znode;
-
insert(heap, z, k); // 结点z按上界的值插入堆中
-
delete xnode;
-
x = delete_max(heap, k); // 获得堆顶元素作为新的父亲结点
-
xnode = x.p;
-
}
-
v = xnode->p;
-
for( i=0; i<n; i++){ // 取装入背包中物体在排序前的序号
-
if(xnode->s1[i]){
-
obx[i] = ob[i].num;
-
}else{
-
obx[i] = -1;
-
}
-
}
-
delete xnode;
-
/* for(i=1; i<=k; i++) {
-
delete heap[i].p;
-
}*/
-
delete heap;
-
return v; // 返回背包中物体的价值
-
}
-
-
int main(){
-
OBJECT ob[N];
-
double m;
-
int n, i;
-
int obx[N];
-
-
cout<<"请输入背包载重：";
-
cin>>m;
-
-
cout<<"请输入物品个数：";
-
cin>>n;
-
-
cout<<"请输入物品重量：";
-
for(i=0; i<n; i++){
-
cin>>ob[i].w;
-
}
-
-
cout<<"请输入物品价值：";
-
for(i=0; i<n; i++){
-
cin>>ob[i].p;
-
}
-
-
double v = knapsack_bound(ob, m, n, obx);
-
-
cout<<"装入背包的物体："<<endl;
-
for( i=0; obx[i]>=0&&i<n; i++){
-
cout<<obx[i]<<" ";
-
}
-
cout<<endl;
-
cout<<"最优价值："<<v<<endl;
-
-
return 0;
-
}
-
评论 (0)
