递归回溯剪枝法求解01背包问题

#include<stdio.h>
#include<stdlib.h>
#define N 4//最多物品数
#define W 6//背包最大重量
 
struct OBJ{
    int no;
    int w;
    int v;
    double p;
};//定义物品结构体
 
int maxv;
 
struct OBJ A[N+1];
int x[N+1];
 
int bound(int i,int tw,int tv){
    i++;
    while(i<=N&&tw+A[i].w<=W){//若序号为i的物品可以完整放入，计算最大价值
        tw+=A[i].w;
        tv+=A[i].v;
        i++;
    }
    if(i<=N)//如果i不是最后一个物品，则说明未全部放入
        return tv+(W-tw)*A[i].p;//返回未完全放入的最大边界价值
    else
        return tv;//返回当前最大边界价值
}//计算边界最大价值与实际价值最大比较，用于右子树剪枝
 
void dfs(int i,int tw,int tv,int op[]){
    if(i>N){//寻找到叶子节点开始更新最大价值
        maxv=tv;
        for(int j=1;j<=N;j++)
            x[j]=op[j];//解向量存储物品情况
    }
    else{
        if(tw+A[i].w<=W){
            op[i]=1;
            dfs(i+1,tw+A[i].w,tv+A[i].v,op);
        }//左子树剪枝
        if(bound(i,tw,tv)>maxv){
            op[i]=0;
            dfs(i+1,tw,tv,op);
        }
    }
}
 
int main(){
    maxv=0;
    int op[N+1]={0,0,0,0,0};
    //结构体数组赋值
    A[1].no=3;
    A[2].no=2;
    A[3].no=4;
    A[4].no=1;
    //按p值递减排序,剪枝越多
    A[1].w=2;
    A[2].w=3;
    A[3].w=1;
    A[4].w=5;
 
    A[1].v=3;
    A[2].v=4;
    A[3].v=1;
    A[4].v=4;
 
    //p=v/w，即为物品性价比
    for(int i=1;i<=N;i++)
        A[i].p=(double)A[i].v/A[i].w;
 
    dfs(1,0,0,op);
 
    for(int i=1;i<=N;i++)
        printf("%d ",x[i]);
    printf("\n最大价值为%d",maxv);
}

图1

图2

-------该算法摘自《算法设计与分析(第2版)》